题解 P6304 【[eJOI2018]山】

一叶知秋。 · 2020-06-01 16:09:25 · 题解

DP裸题，考虑怎么设状态

设 f[i][j][x][y] (i \le n,j\le(i+1)/2,x<2,y<2)

表示前 i 座山中有 j 座用来造房子，第 i-1 座山与第 i 座山的状态分别为 x 和 y （ 0 表示不建房子， 1 反之）的最小花费，然后转移，最后输出时在几种状态中取小即可

具体实现看代码：

#include<cstdio>
#include<cctype>

#define maxn 5555

inline int read(){
    int r=0,f=0;
    char c;
    while(!isdigit(c=getchar()))f|=(c=='-');
    while(isdigit(c))r=(r<<1)+(r<<3)+(c^48),c=getchar();
    return f?-r:r;
}

inline int min(int a,int b){
    return a<b?a:b;
}

inline int val(int x){
    return x<0?0:x;
}

int n,a[maxn],f[maxn][maxn][2][2];

int main(){
    freopen("1.in","r",stdin);
    freopen("1.out","w",stdout);
    n=read();
    for(int i=1;i<=n;i++){
        a[i]=read();
        f[i][0][1][0]=1e9+10;
        for(int j=1;j<=((n+1)>>1);j++)
            for(int x=0;x<2;x++)
                for(int y=0;y<2;y++)
                    f[i][j][x][y]=1e9+10;
    }
    f[1][0][0][0]=f[1][1][0][1]=0;
    a[0]=1e9;
    for(int i=2;i<=n;i++)
        for(int j=1;j<=((i+1)>>1);j++){
            f[i][j][0][0]=min(f[i-1][j][1][0],f[i-1][j][0][0]);
            //这条转移显然
            f[i][j][1][0]=f[i-1][j][0][1]+val(a[i]-a[i-1]+1);
            //因为不能挨着建，所以[1][0]只能由[0][1]转移而来
            f[i][j][0][1]=min(f[i-1][j-1][0][0]+val(a[i-1]-a[i]+1),f[i-1][j-1][1][0]+val(min(a[i-2]-1,a[i-1])-a[i]+1));
            //注意，如果是由[1][0]转移过来的话，那么第i-1座山已经小于a[i-2]了，不需要算两遍
        }
    for(int i=1;i<=((n+1)>>1);i++){
        int ans=1e9+10;
        for(int x=0;x<2;x++)
            for(int y=0;y<2;y++)
                ans=min(ans,f[n][i][x][y]);
        printf("%d ",ans);
    }
    return 0;
}