P1651 塔

· · 个人记录

P1651 塔 P1373 小a和uim之大逃离 很明显的dp，但是数据范围很玄学：对于100%的数据，N≤50，每块木块的高度h满足1≤h≤500000，所有木块的高度总和≤500000。
如果想要用f[i][j][k]表示选i个积木时第一个塔的高度为j，第二个为k的状态时，空间会炸的很惨，根本装不下，那么我们该怎么解决这个问题呢，这里提供一个新的思路：
我们不妨用f[i][j]表示选了i个积木时两坨积木的高度差为j，所存的是较高的积木的高度；
吼，状态我们掌握了，接下来看转移： f[i][j]=max(f[i-1][j],f[i-1][j+h[i]]); 表示我将这块积木放到了高的那边， 从而我的高度差会加上我这块积木的高度 同时与不放这块积木取最优，解决了不选积木i的情况 如果当前高度差大于我要放的积木的高度：
f[i][j]=max(f[i][j],f[i-1][j-h[i]]+h[i]);
表示我将这块积木放到了低的那边使我的高度差减小h[i] 并且高的依然高，矮的依然矮 如果当前高度差小于我要放的积木的高度：
f[i][j]=max(f[i][j],f[i-1][h[i]-j]+j);
表示我高度差变为h[i]-j， 原来高的会变矮，原来矮的会变高

吼的，下面是AC代码 

#include<bits/stdc++.h>
using namespace std;
int n,h[55],f[55][500000],sum;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&h[i]);
        sum+=h[i];
    }
    memset(f,128,sizeof(f));//全标记为不可达到的状态
//  cout<<f[0][0];
    f[0][0]=0;//注意赋初值
    for(int i=1;i<=n;i++){
        for(int j=sum;j>=0;j--){
            f[i][j]=max(f[i-1][j],f[i-1][j+h[i]]);
            if(j>=h[i])f[i][j]=max(f[i][j],f[i-1][j-h[i]]+h[i]);
            else{
                f[i][j]=max(f[i][j],f[i-1][h[i]-j]+j);
            }
        }
    }
    if(f[n][0])cout<<f[n][0];
    else cout<<-1;
}

在写完之后我们可以发现对于每个状态f[i][]它的转移只与f[i-1][]的状态有关，所以我们还可以进一步优化空间，将数组的第一维压掉，对于某些题目而言，在压维之后循环的顺序会发生变化，不然GG（不过学长说noip中会卡压维的顶多只有10分，还是不要冒这个险比较好）