题解 P1651 【塔】

· · 题解

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

换一种理解方式

令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;
}