首页 > 代码库 > [hrbust acmbook] dp优化-改进状态表示
[hrbust acmbook] dp优化-改进状态表示
把n个数字,分成m组,每组的和不能大于t。分组必须按顺序
三维dp[i][j][k]: 显然状态太多,nmt为1000就爆了,i表示前i个数字,j表示分成j组,k表示最后一组已经放的数的和
关键是改进,改成二维
dp[i][j]:i表示前i个元素,j表示取j个数,dp数组是一个结构体数组,表示(x,y)
也就是说,dp数组存的是在前i个数中取j个数,需要的最少的组数和最后一组的已经放的数的和
好的放数方法,组数越少当然越好,组数一样的时候,y越小越好
这种思想很巧妙
UVA 473
#include<cstdio> #include<cstring> #include<cctype> #include<algorithm> using namespace std; int readint() { char a; int num=0; a=getchar(); while(!isdigit(a)) a=getchar(); while(isdigit(a)) { num=num*10+a-‘0‘; a=getchar(); } return num; } struct point { int x; int y; }; point dp[1005][1005]; int a[1005]; int main() { int kase; scanf("%d",&kase); for(int x=1;x<=kase;x++) { int n,t,m; scanf("%d%d%d",&n,&t,&m); for(int i=0;i<=n;i++) { for(int j=0;j<=n;j++) { dp[i][j].x=10000; dp[i][j].y=0; } } for(int i=0;i<=n;i++) { dp[i][0].x=1; dp[i][0].y=0; } for(int i=1;i<=n;i++) a[i]=readint(); for(int i=1;i<=n;i++) { for(int j=1;j<=i;j++) { dp[i][j]=dp[i-1][j]; if(dp[i-1][j-1].y+a[i]<=t) { if(dp[i-1][j-1].x<dp[i][j].x) { dp[i][j].x=dp[i-1][j-1].x; dp[i][j].y=dp[i-1][j-1].y+a[i]; } else if(dp[i-1][j-1].x==dp[i][j].x) { if(dp[i-1][j-1].y+a[i]<dp[i][j].y) { dp[i][j].y=dp[i-1][j-1].y+a[i]; } } } else { if(dp[i-1][j-1].x+1<dp[i][j].x) { dp[i][j].x=dp[i-1][j-1].x+1; dp[i][j].y=a[i]; } else if(dp[i-1][j-1].x+1==dp[i][j].x) { if(a[i]<dp[i][j].y) { dp[i][j].y=a[i]; } } } } } int ans=0; for(int i=1;i<=n;i++) { if(dp[n][i].x<=m) ans=i; } if(x!=1) printf("\n"); printf("%d\n",ans); } return 0; }
[hrbust acmbook] dp优化-改进状态表示
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。