题目链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=1059
分析：dp[i][j]表示前i个石头组成两座塔高度差为j的较低塔最大高度
状态转移：
每次石头都有三种方法：
1.放在高塔上：dp[i][j]=max(dp[i][j+t],dp[i][j]);低塔不变
2.放在低塔上：1)dp[i][j]=max(dp[i][j-t],dp[i][j]);低塔仍是较低塔
2)dp[i][j]=max(dp[i][t-j],dp[i][j]);低塔超过高塔
3.低塔高塔都不放
#include #include #include #include #include #include #include #include #include <set> #include #define LL long long #define inf 1<<30 #define mod 1000000007 using namespace std; int dp[105][2010]; int main() { int n,t; while(scanf("%d",&n)>0) { if(n<0)break; memset(dp,-1,sizeof(dp)); dp[0][0]=0; for(int i=1;i<=n;i++) { scanf("%d",&t); memcpy(dp[i],dp[i-1],sizeof(dp[i-1])); for(int j=0;j<=2000;j++) { if(dp[i-1][j]!=-1) { int x=dp[i-1][j]; int y=dp[i-1][j]+j; if(x+t<=y) { dp[i][j-t]=max(dp[i][j-t],x+t); } else { dp[i][t-j]=max(dp[i][t-j],y); } dp[i][j+t]=max(dp[i][j+t],x); } } } if(dp[n][0]<=0)puts("Sorry"); else printf("%d\n",dp[n][0]); } }
为了节省空间，还可以用滚动数组来实现dp
#include #include #include #include #include #include #include #include #include <set> #include #define LL long long #define inf 1<<30 #define mod 1000000007 using namespace std; int dp[2][2010]; int main() { int n,t; while(scanf("%d",&n)>0) { if(n<0)break; memset(dp,-1,sizeof(dp)); dp[0][0]=0; int pre=0,now=1; for(int i=1;i<=n;i++) { scanf("%d",&t); memcpy(dp[now],dp[pre],sizeof(dp[now])); for(int j=2000;j>=0;j--) { if(dp[pre][j]!=-1) { int x=dp[pre][j]; int y=dp[pre][j]+j; if(x+t<=y) { dp[now][j-t]=max(dp[now][j-t],x+t); } else { dp[now][t-j]=max(dp[now][t-j],y); } dp[now][j+t]=max(dp[now][j+t],x); } } swap(pre,now); } if(dp[pre][0]<=0 )puts("Sorry"); else printf("%d\n",dp[pre][0]); } }
zoj2059（经典dp）
京公网安备 11010802041100号