自动搬运

查看原文

来自洛谷，原作者为

	FLYing **

搬运于2025-08-24 21:27:32，当前版本为作者最后更新于2019-07-14 14:26:26，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

和已有的解法是同一种思路，但是可以简化代码的打法。

换一种理解方式

令Fij表示前i个积木，其中第一堆积木减去第二堆积木的差值为j时左边积木的高度。

这样一来就无需考虑两边高度的大小问题了。

于是对于Fij的转移，有三种情况：

①物品i不选，则f[i][j] = max(f[i][j], f[i-1][j]);

②物品i放左边，则f[i][j] = max(f[i][j], f[i-1][j-a[i]]+a[i]);

③物品i放右边，则f[i][j] = max(f[i][j], f[i-1][j+a[i]]);

三种情况取一个最大值

找到最大的 j等于0 时的fij即可。

初始值为F[0][0]等于0，其它情况为最小值代表该高度无法表示出来，不参与转移。

这样一来就会出现一个问题，j这一维会出现负数。因为j表示的是第一堆减去第二堆的差值，这里只需根据题目的数据范围，将j加上个500000即可，即500000代表0上下界是0到1000000。

最后加个动数组优化空间

#include<cstdio>
#include<cstring>
#define maxn 1000039
using namespace std;
int f[2][maxn], N, a[51], ans;
int max(int a, int b){return a>b?a:b;}
int max(int a, int b, int c){return max(a, max(b, c));}
int main(){
	freopen("1.in", "r", stdin);
	memset(f, -0x3f3f3f3f, sizeof(f));
	scanf("%d", &N);
	f[0][500000] = 0;
	for(int i = 1; i < N+1; i++)scanf("%d", &a[i]);
	for(int i = 1; i < N+1; i++)
		for(int j = 0; j < 1000000+1; 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;
}