本文主要是介绍hdu 4502(dp)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
刚开始做，想到的方法是，按照时间顺序，从小到大，排完序之后，在节点i处的最大值一定在满足条件的节点j后。
满足的条件是：第j个节点结束时间小于i节点的开始时间。
那么j可以为1<=j<i;
即 dp[i]=max(dp[i],dp[j])+c[i] (1<=j<i)
#include <iostream>
#include<algorithm>
using namespace std;struct work
{long s,e,c;
}w[1005];int cmp(work w1,work w2)
{if(w1.s==w2.s&&w1.e==w2.e)return w1.c>=w2.c;if(w1.s==w2.s)return w1.e<w2.e;return w1.s<w2.s;
}int main()
{
// freopen("in.txt","r",stdin);int t;int m,n;int dp[1005];int k=0;long a,b,c;scanf("%d",&t);while(t--){scanf("%d %d",&m,&n);k=1;for(int i=1;i<=n;i++){scanf("%ld %ld %ld",&a,&b,&c);if(a>=1&&b<=m) { w[k].s=a; w[k].e=b; w[k].c=c; k++; }}sort(w+1,w+k,cmp);for(int i=1;i<k;i++)dp[i]=0;if(w[1].s<=m&&w[1].e<=m)dp[1]=w[1].c;for(int i=2;i<k;i++){for(int j=1;j<i;j++) //从1开始到i-1遍历，只要w[j].e<w[i].s，说明i可以跟在j的后面if(w[j].e<w[i].s&&dp[j]>dp[i]) //找到最大值dp[i]=dp[j];dp[i]+=w[i].c; //加上本身的值}long max_c=0;for(int i=1;i<k;i++) //所有的节点搜完最大值之后，最大值并不一定在dp[k-1]中if(dp[i]>max_c)max_c=dp[i];printf("%ld\n",max_c);} return 0;
}
后来，看了下discuss。看到了01背包的做法。
dp[i][j]=max(dp[i-1][j],dp[i][s[i]-1]+c[i]) j>=e[i];
#include <iostream>
#include<algorithm>
using namespace std;struct work
{long s,e,c;
}w[1005];int cmp(work w1,work w2)
{if(w1.s==w2.s&&w1.e==w2.e)return w1.c>=w2.c;if(w1.s==w2.s)return w1.e<w2.e;return w1.s<w2.s;
}int max(int a,int b)
{return a>b?a:b;
}int main()
{
// freopen("in.txt","r",stdin);int t;int m,n;int dp[110];int k=0;long a,b,c;scanf("%d",&t);while(t--){scanf("%d %d",&m,&n);k=1;for(int i=1;i<=n;i++){scanf("%ld %ld %ld",&a,&b,&c);if(a>=1&&b<=m) { w[k].s=a; w[k].e=b; w[k].c=c; k++; }}sort(w+1,w+k,cmp);for(int i=0;i<=m;i++)dp[i]=0;for(int i=1;i<k;i++)for(int j=m;j>=w[i].e;j--)dp[j]=max(dp[j],dp[w[i].s-1]+w[i].c);printf("%d\n",dp[m]);}return 0;
}
这篇关于hdu 4502(dp)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
