首页 > 代码库 > zoj2059（经典dp）
zoj2059（经典dp）
题目链接：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 <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using 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 <cstdio>#include <cstring>#include <cmath>#include <iostream>#include <algorithm>#include <queue>#include <cstdlib>#include <vector>#include <set>#include <map>#define LL long long#define inf 1<<30#define mod 1000000007using 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）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。