yzoj P1126 塔 题解

题意:给n个积木，搭成两个高度相同的塔，问最高高度

正解是dp

答案在dp[n][0]

代码

#include<bits/stdc++.h>
using namespace std;
int f[2][1000050],n,a[51],ans;
int main(){ 
	memset(f,-0x3f,sizeof(f));
	scanf("%d",&n);
	for(int i=1;i<=n;++i){
		scanf("%d",&a[i]);
	}
	f[0][500000]=0;
	for(int i=1;i<=n;++i){
		for(int j=0;j<=1000000;++j){
			 f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j]);
			 if(j-a[i]>=0)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j-a[i]]+a[i]);
			 if(j+a[i]<=1000000)f[i%2][j]=max(f[i%2][j],f[(i%2)^1][j+a[i]]);
             if(j==500000)ans=max(ans,f[i%2][j]);
		}
	}
	printf("%d",ans==0?-1:ans);
	return 0;
}