Luogu P1651 塔

April 14, 2019

1108 views

1068 words

[题目链接](https://www.luogu.org/problemnew/show/P1651 "题目链接")

* * *

突然发现，我还是太菜了。 这道题做了一个半小时，开始的一个小时想的都是错的，后来还是看了题解，本来我想的是用bool数组$f\[i\]\[j\]$来表示从木块中选i个木块能否组成j的高度，用0和1表示。后来打了70分（数据好水）才发现这有后效性。

#### 正解

因为题目中讲能否选择几个木块构成两个高度相同的塔，要求输出这个塔的最大高度，那么就可以想到，使用$f\[i\]\[j\]$来表示选到第i个时，且两个塔的高度差为j时，较高的那个塔的高度，这样便有四个状态可以转移。 - 不放第i个：$f\[i\]\[j\]=f\[i-1\]\[j\]$ - 把第i个放到较矮的塔上，矮塔还是矮塔：$f\[i\]\[j\]=max(f\[i\]\[j\],f\[i-1\]\[j+a\[i\]\])$ - 放到较高的塔上，高塔当然高：$f\[i\]\[j\]=max(f\[i\]\[j\],f\[i-1\]\[j-a\[i\]\]+a\[i\])$ - 放到较低的塔上，低塔变成高塔：$f\[i\]\[j\]=max(f\[i\]\[j\],f\[i-1\]\[a\[i\]-j\]+j)$ 综上，代码如下：
```cpp
    #include<bits/stdc++.h>
    using namespace std;
    
    int n,a[55],sum;
    int f[55][500005];
    
    int main(){
        cin>>n;
        for(int i=1;i<=n;i++){
            cin>>a[i];
            sum+=a[i];
        }
        memset(f,-0x3f,sizeof(f));
        f[0][0]=0;
        for(int i=1;i<=n;i++){
            for(int j=sum;j>=0;j--){
                f[i][j]=max(f[i][j],f[i-1][j]);
                f[i][j]=max(f[i][j],f[i-1][j+a[i]]);
                if(j>=a[i]) f[i][j]=max(f[i][j],f[i-1][j-a[i]]+a[i]);
                if(j<=a[i]) f[i][j]=max(f[i][j],f[i-1][a[i]-j]+j);
            }
        }
        if(f[n][0]<=0) cout<<"-1";
        else cout<<f[n][0];
        return 0;
    }
```

Last modification：March 14, 2020