HDU 3236 Gift Hunting (程序猿的哄女朋友方式)

哄女朋友开心的错误示范。
题意：你和你女朋友（不，你没有）去购物，你有两个购物券v1，v2，不能叠加使用，所购买的礼物的和不超过券的值就可以买，你女朋友过生日，可以免费带走一个礼物。礼物有价格p和女朋友开心值v，有些礼物是你女朋友必须要的，你必须要买的。求女朋友开心值（所得到的v的和）的最大值。
思路：01背包的变形，二维背包、带约束条件的背包、（仅）可消除一次价格、提醒你没有女朋友 。
dp[i][j][k]表示v1使用了i元,v2使用了j元,k==1代表你女朋友已经免费带走一个商品（技能CD中 ） 。
状态转移方程：
dp[j][k][1] = max(dp[j][k][1], dp[j][k][0]+v[i]);
dp[j][k][0] = max(dp[j][k][0], dp[j-p[i]][k][0]+v[i]);
dp[j][k][1] = max(dp[j][k][1], dp[j-p[i]][k][1]+v[i])
dp[j][k][0] = max(dp[j][k][0], dp[j][k-p[i]][0]+v[i]);
dp[j][k][1] = max(dp[j][k][1], dp[j][k-p[i]][1]+v[i]);
其中从dp[j][k][0]到dp[j][k][1]要放在前面，否则会重复记一个。

那么怎么处理女朋友必买的物品呢？
我的思路是在必买的物品加上1000000，这里的物品的价格和最大不过300*1000=300000，在加上后必买的物品的价格会严格高于其他物品，且不会出现其余物品和加起来大于1000000的情况，在结尾判断一下ans整除1000000的值，这个值就是你必买礼物的个数了，输出的时候记得减掉，输出时候要两个\n…

代码：

#include <algorithm> #include <iostream> #include <cstdio> #include <stack> #include <vector> #include <string> #include <cstring> #include <cmath> #include <queue> #include <set> #include <map> #include <list> #include <ctime>using namespace std;#define ll long long #define ld long double #define inf 0x3f3f3f3f #define INF 0x3f3f3f3f3f3f3f3f#define EXP 1e-8 #define MOD 1000000007 #define N 50005#define random(x) rand()%x+1inline int next_int() {char c;while(c = getchar(), c < '0' || c > '9');int r = c-'0';while(c = getchar(), c >= '0' && c <= '9')r = r*10+c-'0';return r; }int n, v1, v2; int dp[502][55][2]; int p[505]; int v[505]; int need[505]; int numbOfNeed; int ans;void init() {memset(dp, 0, sizeof(dp));memset(p, 0, sizeof(p));memset(v, 0, sizeof(v));memset(need, 0, sizeof(need));numbOfNeed = 0;ans = 0; }int main() { #ifdef Wang_Zhifengfreopen("in.txt", "r", stdin); #endifint cnt = 1;while(scanf("%d%d%d", &v1, &v2, &n)) {if(n==0)break;init();for(int i = 0; i < n; ++i) {scanf("%d%d%d", &p[i], &v[i], &need[i]);if(need[i]==1) {numbOfNeed++;v[i] += 1000000;}}for(int i = 0; i < n; ++i) {for(int j = v1; j >= 0; --j) {for(int k = v2; k >= 0; --k) {dp[j][k][1] = max(dp[j][k][1], dp[j][k][0]+v[i]);if(j >= p[i]) {dp[j][k][0] = max(dp[j][k][0], dp[j-p[i]][k][0]+v[i]);dp[j][k][1] = max(dp[j][k][1], dp[j-p[i]][k][1]+v[i]);}if(k >= p[i]) {dp[j][k][0] = max(dp[j][k][0], dp[j][k-p[i]][0]+v[i]);dp[j][k][1] = max(dp[j][k][1], dp[j][k-p[i]][1]+v[i]);}}}}for(int j = v1; j >= 0; --j) {for(int k = v2; k >= 0; --k) {ans = max(ans, dp[j][k][0]);ans = max(ans, dp[j][k][1]);}}printf("Case %d: %d\n\n", cnt++, ans >= numbOfNeed*1000000 ? ans-numbOfNeed*1000000 : -1);}return 0; }

总结

以上是生活随笔为你收集整理的HDU 3236 Gift Hunting (程序猿的哄女朋友方式)的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。