题目概述

$x$ 轴上按顺序有 $n$ 座山，每座山有海拔 $h_i$ ，如果一座山比周围两个山高就可以建房子。可以花费 $1$ 的代价把山铲去 $1$ 的海拔，问建 $1\sim\lceil{n\over 2}\rceil$ 个房子的最小代价。

解题报告

斯波DP题，但是我又双叒叕看错题目了+写丑了。

一个地方要建房子肯定只和前面两个有没有建房子有关系，所以定义 $f_{i,j,0/1}$ 表示前 $i$ 座山建了 $j$ 个房子，$i$ 有没有建房子的最优解。

每次从 $f_{i-1}$ 和 $f_{i-2}$ 转移一下就好了。

示例程序

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=5000;

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

#define val(x,y) (max((x)-(y),0))
int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    scanf("%d",&n);for (int i=1;i<=n;i++) scanf("%d",&a[i]);
    memset(f,63,sizeof(f));f[0][0][0]=0;f[1][1][1]=val(a[2],a[1]-1);
    for (int i=0;i<n;i++)
        for (int j=0;j<=(i+1>>1);j++){
            f[i+1][j][0]=min(f[i+1][j][0],min(f[i][j][0],f[i][j][1]));
            if (i+1<n){
                f[i+2][j+1][1]=min(f[i+2][j+1][1],f[i][j][0]+val(a[i+1],a[i+2]-1)+val(a[i+3],a[i+2]-1));
                f[i+2][j+1][1]=min(f[i+2][j+1][1],f[i][j][1]+val(min(a[i+1],a[i]-1),a[i+2]-1)+val(a[i+3],a[i+2]-1));
            }
        }
    for (int i=1;i<=(n+1>>1);i++) printf("%d",min(f[n][i][0],f[n][i][1])),i<(n+1>>1)?putchar(' '):puts("");return 0;
}