hdu 3236

终于能过这道题了，算是背包必做题之一吧

/*
 * Author: rush
 * Created Time:  2010年12月12日 星期日 12时34分31秒
 * File Name: icpc/hdu3236_3.cpp
 */
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
#define out(v) cout << #v << ": " << (v) << endl
using namespace std;
typedef long long LL;

const int oo = 0x3f3f3f3f;
int V1, V2, n, id = 1;
int P[305], H[305], S[305];
int dp[505][55][2], x, y;
#define update(t, x, y, z, add) if (0 <= x && 0 <= y) t = max(t, dp[x][y][z] + add)
/*
void update(int &t, int x, int y, int z, int add) {
	if (x < 0 || y < 0) return;
	t = max(t, dp[x][y][z] + add);
}
*/
int main()
{
	while (scanf("%d%d%d", &V1, &V2, &n) != EOF) {
		if (V1 == 0 && V2 == 0 && n == 0) break;
		for (int i = 0; i < n; ++i)
			scanf("%d%d%d", &P[i], &H[i], &S[i]);
		memset(dp, 0, sizeof(dp));
		for (int i = 0; i < n; ++i) {
			for (int a = V1; a >= 0; --a)
				for (int b = V2; b >= 0; --b)
					for (int c = 1; c >= 0; --c) {
						if (S[i]) dp[a][b][c] = -oo;
						update(dp[a][b][c], a - P[i], b, c, H[i]);
						update(dp[a][b][c], a, b - P[i], c, H[i]);
						//if (0 <= a - P[i]) dp[a][b][c] = max(dp[a][b][c], dp[a - P[i]][b][c] + H[i]);
						//if (0 <= b - P[i]) dp[a][b][c] = max(dp[a][b][c], dp[a][b - P[i]][c] + H[i]);
						if (c == 1) {
							//dp[a][b][c] = max(dp[a][b][c], dp[a][b][0] + H[i]);
							update(dp[a][b][c], a, b, 0, H[i]);
						}
					}
		}
		int ans = dp[V1][V2][1];
		printf("Case %d: %d\n", id++, ans < 0 ? -1 : ans);
		printf("\n");
	}
    return 0;
}