小x买年货

10.17模拟T2

春节将至，小x要去超市购置年货，于是小x去了自己经常去的都尚超市。刚到超市，小x就发现超市门口聚集一堆人。用白云女士的话说就是：“那家伙，那场面，真是人山人海，锣鼓喧天，鞭炮齐呤，红旗招展。那可真是相当的壮观啊！”。
好奇的小x走过去，奋力挤过人群，发现超市门口贴了一张通知，内容如下：值此新春佳节来临之际，为了回馈广大顾客的支持和厚爱，特举行春节大酬宾、优惠大放送活动。凡是都尚会员都可用会员积分兑换商品，凡是都尚会员都可免费拿 k 件商品，
blablabla…
还没看完通知，小x就高兴的要死，因为他就是都尚的会员啊。迫不及待的小x在超市逛了一圈发现超市里有 n 件他想要的商品。小x顺便对这 n 件商品打了分，表示商品的实际价值。小x发现身上带了 v1 的人民币，会员卡里面有 v2 的积分。他想知道他最多能买多大价值的商品。
由于小x想要的商品实在太多了，他算了半天头都疼了也没算出来，所以请你这位聪明的程序员来帮帮他吧。

输入
第一行是四个整数 n，v1，v2，k；

然后是 n 行，每行三个整数 a，b，val，分别表示每个商品的价钱，兑换所需积分，实际价值。

其中，1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100。

Ps. 只要钱或者积分满足购买一件商品的要求，那么就可以买下这件商品。

输出
输出能买的最大价值。

样例输入
5 1 6 1

4 3 3

0 3 2 2 3 3

3 3 2

1 0 2

样例输出
12

数据范围限制
1 <= n <= 100，0 <= v1, v2 <= 100，0 <= k <= 5，0 <= a, b, val <= 100；

解题思路：比赛的时候看见数据小的很，然后题面的话就很像DP
所以一波判断后，直接开始推DP。
这题对于普通DP不同的是，它有两个条件可以来购买东西，所以我们先确定数组维数至少两维。
然后发现还能上头免费送（那个商城这样干啊，我也去……），一开始思路是贪心出按价格排序（当时思路很简单，我不买对的只买贵的还不行吗？）
这就有个问题，不买对的？？？
上头了吗，描述一下反例。假如说我现在选择了完了现在最值得选的，那我还有一个不贵但价值高的很的（比以前的还是差了一点），那你说我是选最贵的价值不高的免费好，还是这个不贵但价值高的好。

又有人说了，我按性价比排序不行吗，实在不行我按价值直接排序它不香吗？（不要忘记，如果排性价比要双关键字排序）
但是，如果按性价比排序我有一个性价比特别高（价格和积分消耗不高，但价值贼高的），那我选完了免费的，自己按价格选的。现在因为价格问题我选不了下面那个既便宜又有价值的，那这就不是最优解了（可能有点绕，再回来想一想我比赛的时候想这个点出对拍程序用了半小时）。同理，按价值排序也会被这样卡住。

所以我们选择一个冒险的决定，再开一个维度表示免费次数还剩多少。想到这里一个转移式就推出来了：设$F_{p,i,j,k}$为在选到P个物品的时候，还用i元钱，j积分，k免费机会的最大价值。
你可能要问了，这P不是废的吗？
且听我慢慢道来……
所以转移式就是f1=f2=f3=-val[p];
if(i>=a[p]) f1=f[p-1][i-a[p]][j][k];
if(j>=b[p]) f2=f[p-1][i][j-b[p]][k];
if(k>=0) f3=f[p-1][i][j][k+1]+val[p];
f[p][i][j][k]=max(f[p-1][i][j][k],max(max(f1,f2)+val[p],f3));

好似没什么问题呢，好。

淦，怎么回事呢？比赛出来我人没了，要不是第一题给力我这前十估计上头。
这时，我也发现了P好似没有用诶，删了改一下。还有调整一下循环顺序，p,i,j,k（原来p,k,i,j）

10分……

我看到了一个地方，我要是在转移式中拿东西替代一下,这样会不会更准确一点（突发奇想）
说干就干：int find=f[i][j][k];
if(i>=a[p]) find=max(find,f[i-a[p]][j][k]+val[p]);
if(j>=b[p]) find=max(find,f[i][j-b[p]][k]+val[p]);
if(k>0) find=max(find,f[i][j][k-1]+val[p]);
f[i][j][k]=find,ans=max(ans,f[i][j][k]);

咦，这是……满分，我的*****
最后，附上代码：

#include<cstdio>
using namespace std;
int n,v1,v2,k,ans=-100005;
int a[105],b[105],val[105];
int f[105][105][7];
int max(int xx,int yy)
{if(xx>yy) return xx;else return yy;
}
int main()
{freopen("purcha.in","r",stdin);freopen("purcha.out","w",stdout);scanf("%d%d%d%d",&n,&v1,&v2,&k);for(int i=1;i<=n;++i) scanf("%d%d%d",&a[i],&b[i],&val[i]);for(int k=1;k<=n;++k)for(int x=k;x>=0;--x)for(int i=v1;i>=0;--i)for(int j=v2;j>=0;--j){int find=f[i][j][x];if(i>=a[k]) find=max(find,f[i-a[k]][j][x]+val[k]);if(j>=b[k]) find=max(find,f[i][j-b[k]][x]+val[k]);if(x>0) find=max(find,f[i][j][x-1]+val[k]);f[i][j][x]=find,ans=max(ans,f[i][j][x]);}printf("%d",ans);return 0;
} 

好啦，谢谢您的观看！