寒假集训——GiftHunting
题目链接
题意:买东西,有两张购物卷,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