首页 > 代码库 > 01背包水题篇之HDU3466——Proud Merchants

01背包水题篇之HDU3466——Proud Merchants


这是个好题,菜鸟刚学dp,这题把我以前的想法全都给完完全全的颠覆了。其实是自己没了解无后效性的概念。

然后我去开开心心滴跑去问队长:”队长,队长,怎么理解动归的无后效性啊???“

学长很深沉滴对我说:”做多了就会了“

"噢噢”(好吧)

然后学长又补了句:“能构成有向无环图的都能用DP搞."

我心里想:”队长就知道搞妹~~~。“

默默去翻小白书看看DAG去了。


为了搞清楚这题怎么写,操了度娘千百遍,还是没搞定。。。 肿么办,弱菜这么水怎么破


又是贴代码环节(好讨厌啊,压根就不理解为毛线 要对 q-p按从小到大排序啊,虽然大牛都说是因为无后效性的原因,我只能说:不明觉厉啊,有木有,德玛西亚~)


#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
using namespace std;
int dp[5001];
struct node
{
    int p,q,v;
}p[501];
bool cmp(node x,node y)
{
    return x.q-x.p<y.q-y.p;
}
int main()
{
    int n,m;
    while(cin>>n>>m){
        for(int i=0;i<n;i++){
            scanf("%d%d%d",&p[i].p,&p[i].q,&p[i].v);
        }
        sort(p,p+n,cmp);//排完序就是赤裸裸的01了
        memset(dp,0,sizeof dp);
        for(int i=0;i<n;i++){
            for(int j=m;j>=p[i].q;j--){
                dp[j]=max(dp[j],dp[j-p[i].p]+p[i].v);
            }
        }
        cout<<dp[m]<<endl;
    }
    return 0;
}<span style="color:#66cccc;">
</span>