P1509 找啊找啊找GF

题目背景

“找啊找啊找 GF，找到一个好 GF，吃顿饭啊拉拉手，你是我的好 GF。再见。”

“诶，别再见啊…”

七夕… 七夕… 七夕这个日子，对于 sqybi 这种单身的菜鸟来说是多么的痛苦… 虽然他听着这首叫做“找啊找啊找 GF”的歌，他还是很痛苦。为了避免这种痛苦，sqybi 决定要给自己找点事情干。他去找到了七夕模拟赛的负责人 zmc MM，让她给自己一个出题的任务。经过几天的死缠烂打，zmc MM 终于同意了。

但是，拿到这个任务的 sqybi 发现，原来出题比单身更让人感到无聊 -_- … 所以，他决定了，要在出题的同时去办另一件能够使自己不无聊的事情——给自己找 GF。

题目描述

sqybi 现在看中了 $^_^。$

sqybi 希望搞到尽量多的 MM 当自己的 GF，这点是毋庸置疑的。但他不希望为此花费太多的时间（毕竟七夕赛的题目还没出），所以他希望在保证搞到 MM 数量最多的情况下花费的总时间最少。

sqybi 现在有

注意 sqybi 在一个时刻只能去泡一个 MM ——如果同时泡两个或以上的 MM 的话，她们会打起来的…

输入格式

输入的第一行是

接下来有

最后一行有两个整数，分别为

输出格式

你只需要输出一行，其中有一个整数，表示 sqybi 在保证 MM 数量的情况下花费的最少总时间是多少。

输入输出样例

输入 #1

输出 #1

说明/提示

sqybi 说：如果题目里说的都是真的就好了…

sqybi 还说，如果他没有能力泡到任何一个 MM，那么他就不消耗时间了（也就是消耗的时间为

【数据规模】

对于 $\%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;
    
}