3338. 双塔问题

i表示前n块 j表示两个塔相差的高度 最后f[n][0] 为答案
1.这块积木不放 f[i-1][j]
2.放在矮的塔上且没超过高塔 f[i-1][j+a[i]]
3.放在高的塔上 f[i-1][j-a[i]]+a[i]
4.放在矮的塔上但超过了高塔 f[i-1][a[i]-j]+j

constintmaxn=102;
constintmaxlen=10000;
intnum[maxn];
intdp[maxn][maxn+maxlen];//使用i块积木，两人绝对值之差为j时的最大高度
//最后要输出的是dp[n][0]
intn;
intmain(){
scanf(“%d”,&n);
intsum=0;
for(inti=1;i<=n;++i){
scanf(“%d”,&num[i]);
sum+=num[i];
}
memset(dp,-1,sizeof(dp));
dp[0][0]=0;
intlen=min(maxlen,sum);
for(inti=1;i<=n;i++){
for(intj=0;j<=len;j++){
dp[i][j]=max(dp[i-1][j],dp[i][j]);
if(j+num[i]<=maxlen)
{
dp[i][j]=max(dp[i][j],dp[i-1][j+num[i]]);
}
if(j<num[i]){
dp[i][j]=max(dp[i][j],dp[i-1][num[i]-j]+j);
}else{
dp[i][j]=max(dp[i][j],dp[i-1][j-num[i]]+num[i]);
}
}//forj
}//fori
if(dp[n][0]==-1)
printf(“0\n”);
else
printf(“%d\n”,dp[n][0]);
return0;
}

n=int(input())
a=list(map(int, input().split()))
m=sum(a)+1
dp=[[-1]*m for _ in range(n)]
dp[0][a[0]]=a[0]
dp[0][0]=0
for i in range(1,n):
for j in range(m):
if dp[i-1][j]!=-1:
dp[i][j]=max(dp[i][j], dp[i-1][j]) # 不放
dp[i][j+a[i]]=max(dp[i][j+a[i]], dp[i-1][j]+a[i]) # 放高的
dp[i][abs(j-a[i])]=max(dp[i][abs(j-a[i])], dp[i-1][j] if j-a[i]>=0 else dp[i-1][j]+a[i]-j) # 放矮的
print(dp[-1][0])