[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.