洛谷 P1651 塔（DP）

题目传送门https://www.luogu.com.cn/problem/P1651

解题思路

设  表示前  个积木，两塔高度差为 （第一个比第二个高多少），的最大高度。

易得：

首先，不选当前的积木：

其次，选当前积木，将它拼到第一个塔上：

最后，选当前积木，将它拼到第二个塔上：

由于，第二维可能为负数，所以，我们可以以 （数组的总和）为 0 刻度线，去 DP。

同时，滚动数组优化空间……

代码

#include<bits/stdc++.h>
using namespace std;

int n,a[51],sum;
int f[2][1005001];
int ans=0;
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
		sum+=a[i];
	}
	memset(f,-0x3f,sizeof f);
	f[0][sum]=0;
	for(int k=1;k<=n;k++)
	{
		int i=k%2;
		for(int j=0;j<=sum*2;j++)
		{
			f[i][j]=f[i xor 1][j];
			if(j-a[k]>=0)
				f[i][j]=max(f[i][j],f[i xor 1][j-a[k]]+a[k]);
			if(j+a[k]<=sum*2)
				f[i][j]=max(f[i][j],f[i xor 1][j+a[k]]);
			if(j==sum)
				ans=max(ans,f[i][j]);
		}
	}
	if(ans)
	cout<<ans;
	else
	cout<<-1;
	return 0;
}