hdu-3466 Proud Merchants（01背包之转移）

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=3466

题目很容易理解，但是如何将其转换为01背包是个问题。

对物品按 qi-pi 的值从小到大排序，因为这样可以保证每次更新的状态值从小到大递增，前面更新过的状态不会影响后面更新的状态。

题目代码：

#include <iostream>
#include<cstdio>
#include<cstring>
#include <algorithm>
using namespace std;
int n,m;
int dp[5005];
struct sa
{
    int p,q,v,u;
}a[505];
int cmp(const sa &a,const sa &b)
{
    return a.u<b.u;
}
int main()
{
    while(~scanf("%d%d",&n,&m))
    {
        for(int i=0;i<n;i++)
        {
            scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v);
            a[i].u=a[i].q-a[i].p;
        }
        sort(a,a+n,cmp);
        memset(dp,0,sizeof(dp));
        for(int i=0;i<n;i++)
        {
            for(int j=m;j>=a[i].p;j--)
            {
                if(j>=a[i].q)
                dp[j]=max(dp[j],dp[j-a[i].p]+a[i].v);
            }
        }
        printf("%d
",dp[m]);
    }
    return 0;
}