[VIJOS P1037]搭建双塔
转载请注明出处:http://danihao123.is-programmer.com/
很不错的题啊……
很容易想到构造三维的状态,但无论时间还是空间都不好。我们可以构造[tex]f[i][delta][/tex]这种状态,表示用前[tex]i[/tex]块水晶,搭建出的双塔高度差为[tex]delta[/tex]时较大塔的高度。显然答案为[tex]f[n][0][/tex]。
转移的时候,要考虑放到高塔上还是低塔上,以及是否会导致高低塔地位对调。
代码:
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int maxn=101,maxV=2001; int d[2][maxV]; int V[maxn]; int main(){ int n,maxj=0; register int i,j,now,pre; scanf("%d",&n); for(i=1;i<=n;i++){ scanf("%d",&V[i]); maxj+=V[i]; } memset(d,-1,sizeof(d)); d[0][0]=0; for(i=1;i<=n;i++){ now=i%2; pre=1-now; for(j=0;j<=maxj;j++){ if(d[pre][j]>=0) d[now][j]=d[pre][j]; if(V[i]<=j){ if(d[pre][j-V[i]]>=0){ d[now][j]=max(d[now][j],d[pre][j-V[i]]+V[i]); } } if(V[i]>j && d[pre][V[i]-j]>=0){ d[now][j]=max(d[now][j],d[pre][V[i]-j]+j); } if(j+V[i]<=maxj && d[pre][j+V[i]]>=0) d[now][j]=max(d[now][j],d[pre][j+V[i]]); } } if(d[1&n][0]<=0) puts("Impossible"); else printf("%d\n",d[1&n][0]); return 0; }
Jul 05, 2023 08:22:00 PM
To give expert news coverage of recent events around the country (India), professional writers have collaborated to develop the question-paper project. Our team consists of professional writers and citizen प्रश्नपत्र.com journalists with a variety of media interests who are dedicated to providing education updates in the public interest while ensuring openness.Our team consists of professional writers and citizen journalists with a variety of media interests who are dedicated to providing education updates in the public interest while ensuring openness.