“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”
“诶，别再见啊…”
七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。
但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。
sqybi 现在看中了 nn 个 MM，我们不妨把她们编号 11 到 nn。请 MM 吃饭是要花钱的，我们假设请 ii 号 MM 吃饭要花 rmb[i]rmb[i] 块大洋。而希望骗 MM 当自己 GF 是要费人品的，我们假设请第 ii 号 MM 吃饭试图让她当自己 GF 的行为（不妨称作泡该 MM）要耗费 rp[i]rp[i] 的人品。而对于每一个 MM 来说，sqybi 都有一个对应的搞定她的时间，对于第 ii 个 MM 来说叫做 time[i]time[i]。sqybi 保证自己有足够的魅力用 time[i]time[i] 的时间搞定第 ii 个 MM ^_^。
sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。
sqybi 现在有 mm 块大洋,他也通过一段时间的努力攒到了 rr 的人品（这次为模拟赛出题也攒 rp 哦~~）。他凭借这些大洋和人品可以泡到一些 MM。他想知道，自己泡到最多的 MM 花费的最少时间是多少。
注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…
输入的第一行是 nn，表示 sqybi 看中的 MM 数量。
接下来有 nn 行，依次表示编号为 1, 2, 3, \ldots , n1,2,3,…,n 的一个 MM 的信息。每行表示一个 MM 的信息，有三个整数：rmbrmb，rprp 和 timetime。
最后一行有两个整数，分别为 mm 和 rr。
你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。
4 1 2 5 2 1 6 2 2 2 2 2 3 5 5
13
sqybi 说：如果题目里说的都是真的就好了…
sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为 00），他要用这些时间出七夕比赛的题来攒 rp…
【数据规模】
对于 20 \%20% 的数据，1 \le n \le 101≤n≤10；
对于 100 \%100% 的数据，1 \le rmb \le 1001≤rmb≤100，1 \le rp \le 1001≤rp≤100，1 \le time \le 10001≤time≤1000。
对于 100 \%100% 的数据，1 \le m, r, n \le 1001≤m,r,n≤100。
题目分析:
题目有两个限制：
1.找到gf的数量最多
2.找到gf的花费时间最少
所以两个dp来求解
对于当前gf，如果泡她的数量比泡除她之外的其他选择好的妹子的数量大，那么就泡，这时候更新当前时间，如果一样多，花费时间的最大值就是泡她和不泡她取max，不然就不泡（说着很绕口，实际很好想）
注意循环rp和money的时候要倒叙循环，因为对于一个妹子，我们只能取一次她的money和rp，而每次f [ i , j ] 的更新总要用到 f [ i - a [ i ] , j - b [ i ] ] ,所以如果正序更新，相当于一个妹子我们泡了两次，不符合题意，所以应该倒叙更新（倒叙相当于妹子只选了一次，因为当前 f 是根据前面的 f 来的，所以如果这样的更新方式那么后面就可以保证每个妹子只泡一次）
#include<bits/stdc++.h> using namespace std; int a[502],b[502],c[502],num[202][202],f[202][202],n; int main() { cin>>n; for(int i=1;i<=n;i++) { cin>>a[i]>>b[i]>>c[i]; } int m,r; cin>>m>>r; for(int i=1;i<=n;i++) { for(int j=m;j>=a[i];j--) { for(int k=r;k>=b[i];k--) { if(num[j][k]<num[j-a[i]][k-b[i]]+1) { num[j][k]=num[j-a[i]][k-b[i]]+1; f[j][k]=f[j-a[i]][k-b[i]]+c[i]; } else if(num[j][k]==num[j-a[i]][k-b[i]]+1) { f[j][k]=min(f[j][k],f[j-a[i]][k-b[i]]+c[i]); } } } } cout<<f[m][r]; return 0; }
原文：https://www.cnblogs.com/yxr001002/p/14109990.html