寒假集训——GiftHunting

coding

题目链接

题意:买东西,有两张购物卷,v1~500,v2~50,物品分两类,一类必须买,一类选择买,并且有一次免费买东西的机会,n~300个东西。问怎么买可以最大,显然两个卷不能混着用。

题解:dp【i】【j】【k】,i和j是钱数,k表示额外的奖励,0代表没用,1代表用过了。两类物品,必须买就一定要选,选择买就是01背包。dp要倒着推(01背包),并且根据k分开写方程。

重点:多维背包,01背包倒着推,额外增加一维。

#include <iostream>

#include <cstdio>

#include <cstring>

#include <string>

#include <cmath>

#include <ctype.h>

#include <limits.h>

#include <cstdlib>

#include <algorithm>

#include <vector>

#include <queue>

#include <map>

#include <stack>

#include <set>

#include <bitset>

#define CLR(a) memset(a, 0, sizeof(a))

#define REP(i, a, b) for(int i = a;i < b;i++)

#define REP_D(i, a, b) for(int i = a;i <= b;i++)

typedef long long ll;

using namespace std;

const int maxn = 300 + 10;

int dp[510][60][3], p[maxn], h[maxn], s[maxn], n;

int v1, v2;

void getDp()

{

memset(dp, -1, sizeof(dp));

dp[0][0][0] = 0;

for(int i = 1; i <= n; i++)

{

for(int a = v1; a >= 0; a--)//倒着推

{

for(int b = v2; b >= 0; b--)//倒着推

{

if(s[i])//必须要买

{

int ans = -1;//因为有额外的一维,要特别注意会不会影响到本物品的其他情况的更新。

if(a - p[i] >= 0 && dp[a - p[i]][b][1] >= 0)

{

ans = dp[a-p[i]][b][1] + h[i];

}

if(b - p[i] >= 0 && dp[a][b - p[i]][1] >= 0)

{

ans = max(ans, dp[a][b - p[i]][1] + h[i]);

}

if(dp[a][b][0] >= 0)

ans = max(ans, dp[a][b][0] + h[i]);

dp[a][b][1] = ans;//一定要买,所以直接赋值

ans = -1;

if(a - p[i] >= 0 && dp[a - p[i]][b][0] >= 0)

{

ans = dp[a-p[i]][b][0] + h[i];

}

if(b - p[i] >= 0 && dp[a][b - p[i]][0] >= 0)

{

ans = max(ans, dp[a][b - p[i]][0] + h[i]);

}

dp[a][b][0] = ans;

}

else

{

int &tmp = dp[a][b][1];//不能直接赋值,而要经过比较,更加要注意先后顺序,不要影响下面

if(a - p[i] >= 0 && dp[a - p[i]][b][1] >= 0)

{

tmp = max(tmp, dp[a-p[i]][b][1] + h[i]);

}

if(b - p[i] >= 0 && dp[a][b - p[i]][1] >= 0)

{

tmp = max(tmp, dp[a][b - p[i]][1] + h[i]);

}

if(dp[a][b][0] >= 0)

tmp = max(tmp, dp[a][b][0] + h[i]);

int &ans = dp[a][b][0];

if(a - p[i] >= 0 && dp[a - p[i]][b][0] >= 0)

{

ans = max(ans, dp[a-p[i]][b][0] + h[i]);

}

if(b - p[i] >= 0 && dp[a][b - p[i]][0] >= 0)

{

ans = max(ans, dp[a][b - p[i]][0] + h[i]);

}

}

}

}

}

}

void solve()

{

getDp();

int ans = -1;

for(int i = 0;i <= v1;i++)

{

for(int j = 0;j <= v2;j++)

{

ans = max(dp[i][j][0], ans);

ans = max(dp[i][j][1], ans);

}

}

if(ans < 0)

{

printf("-1\n");

}

else

{

printf("%d\n", ans);

}

}

int main()

{

// freopen("10Jin.txt", "r", stdin);

//freopen("10Jout.txt", "w", stdout);

int ncase = 0;

while(scanf("%d%d%d", &v1, &v2, &n) != EOF)

{

if(!v1 && !v2 && !n)

break;

++ncase;

printf("Case %d: ", ncase);

REP_D(i, 1, n)

{

scanf("%d%d%d", &p[i], &h[i], &s[i]);

}

solve();

printf("\n");

}

return 0;

}


本文分享 CSDN - ruclion。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。

以上是 寒假集训——GiftHunting 的全部内容, 来源链接: utcz.com/z/508958.html

回到顶部