hdu 3236_C/C++_编程开发_程序员俱乐部

中国优秀的程序员网站程序员频道CXYCLUB技术地图
热搜:
更多>>
 
您所在的位置: 程序员俱乐部 > 编程开发 > C/C++ > hdu 3236

hdu 3236

 2010/12/12 14:52:44  digiter  http://digiter.javaeye.com  我要评论(0)
  • 摘要:终于能过这道题了,算是背包必做题之一吧/**Author:rush*CreatedTime:2010年12月12日星期日12时34分31秒*FileName:icpc/hdu3236_3.cpp*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<algorithm>#include<
  • 标签:
终于能过这道题了,算是背包必做题之一吧
/*
 * 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;
}
  • 相关文章
发表评论
用户名: 匿名