首页 > 代码库 > hdu 3466 Proud Merchants
hdu 3466 Proud Merchants
这道题对q-p进行从小到大排序,举一个比较直观的例子:
4 20
5 15 20
8 12 19
2 16 21
9 11 13
按照q-p排序后每行dp的变化
0 0 0 0 0 0 0 0 0 0 0 13 13 13 13 13 13 13 13 13 13
0 0 0 0 0 0 0 0 0 0 0 13 19 19 19 19 19 19 19 32 32
0 0 0 0 0 0 0 0 0 0 0 13 19 19 19 20 33 39 39 39 39
0 0 0 0 0 0 0 0 0 0 0 13 19 19 19 20 40 41 54 60 60
没排序dp的变化
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 20 20 20 20 20 20
0 0 0 0 0 0 0 0 0 0 0 0 19 19 19 20 20 20 20 20 20
0 0 0 0 0 0 0 0 0 0 0 0 19 19 19 20 40 41 41 41 41
0 0 0 0 0 0 0 0 0 0 0 13 19 19 19 20 40 41 41 41 41
可以明显看出没有排序忽略了8 12 19
5 15 20 是从dp[10]开始更新
8 12 19是从dp[4]开始更新
2 16 21是从dp[12]开始更新
9 11 13是从dp[3]开始更新
#include<iostream> #include<stdio.h> #include<algorithm> using namespace std; struct node{ int p,q,v; }a[505]; int dp[5005]; bool cmp(node a,node b){ return a.q-a.p<b.q-b.p; } int main(){ int n,m,p,q,v; while(cin>>n>>m){ for(int i=0;i<n;i++){ scanf("%d%d%d",&a[i].p,&a[i].q,&a[i].v); } for(int i=0;i<=m;i++) dp[i]=0; sort(a,a+n,cmp); for(int i=0;i<n;i++){ for(int j=m;j>=a[i].q;j--) dp[j]=max(dp[j-a[i].p]+a[i].v,dp[j]); } int ans=0; for(int i=0;i<=m;i++){ if(dp[i]>ans) ans=dp[i]; } cout<<ans<<endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。