HDU 3466 Proud Merchants

题目大意：现在给出商品，有三个参数，记为pi，qi，vi，vi是商品的在你心里价值，pi是商品的价格，qi是你要买商品的时候至少需要的钱然后求可得的最大价值。

单词积累：Merchants 商人 typical 标志性的

题解：首先我们考虑商品A，B，其pi，qi，vi记为pA，qA，vA，pB，qB，vB，我们可以发现，有些买东西的顺序也会决定你可以得到的最大价值，那么怎么才可以使顺序无影响呢？可以这样想，我们如果A，B都要买，先买A，那么需要的资金至少为pA+qB，先买B，那么需要的资金至少为pB+qA，那么想要资金越少，要先买qi-pi大的商品，所以排序一下再背包就可以了。

#include <cstdio>

#include <cstring>

#include <algorithm>

using namespace std;  

struct node

{

    int p,q,v;

}a[];  

int cmp(node x,node y)

{

    return (x.q-x.p)<(y.q-y.p);

}  

int main()

{

    int n,m,i,j;

    int f[];

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

    {

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

            scanf("%d %d %d",&a[i].p,&a[i].q,&a[i].v);

        sort(a,a+n,cmp);

        memset(f,,sizeof(f));

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

         for(j=m;j>=a[i].q;--j)

          if(f[j]<f[j-a[i].p]+a[i].v)f[j]=f[j-a[i].p]+a[i].v;

        printf("%d\n",f[m]);

    }

    return ;

}

巴特西

HDU 3466 Proud Merchants

最新文章

热门文章