3

1 2 3

0 2 

思路：

看到这道题的第一眼，我想到了一道题，2018noipD1T1铺设道路（链接：https://www.luogu.com.cn/problem/P5019），看起来十分相似，于是这道题想用朴素的贪心写，结果果然不对，两道题的区别还是很大，贪心的正确性无法保证，所以还是回来老老实实的写动归。

我们设定一个三维数组f，f[i][j][0]表示前i座山，修建j座房子，且第i座山没有建房子的代价，f[i][j][1]表示前i座山，修建j座房子，且第i座山建有房子的代价。

通过简单的模拟我们可以得到，(1)f[i][j][0]会从f[i-1][j][0]（直接从前一个状态搬过来，前一座山和这座山都不建房子，抹油代价）和f[i-1][j][1]（前一座山已经建了房子，那么就要使这座山的高度低于前一座山的高度，代价为max(0,a[i]-a[i-1]+1)，有0是因为可能这座山的高度原来就低于前一座山的高度）转移过来，转移方程为：f[i][j][0]=max(f[i-1][j][0],f[i-1][j][1]+max(0,a[i]-a[i-1]+1))   (2)f[i][j][1]的处理要比f[i][j][0]的处理相对复杂，在此我们明确一个观点，相邻的两座山不可能都建房子，并且在考虑这座山是否建房子的时候，可以只考虑这座山之前的状态，而不去考虑这座山之后的状态，这座山之后的状态我们可以在之后再处理，因此，f[i][j][1]可以从f[i-2][j-1][0]转移过来，因为第i-2座山没有建房子，所以第i-1座山的高度没有变化，代价为max(0,a[i]-a[i-1]+1)。f[i][j][1]同样可以从f[i-2][j-1][1]转移过来，因为第i-2座山已经建有房子，所以第i-1座山的高度可能会有变化，因此，总代价为：max(0,a[i-1]-(a[i-2],a[i])+1)（大家思考一下，为什么这里总代价不是：max(0,a[i-1]-min(0,a[i-1]-a[i-2]+1)-a[i]+1)) 答案（先思考再看答案）：因为第i-1座山的高度一定比第i-2和i座山低，而这样做只能保证第i-1座山的高度低于第i-2座山的高度，无法保证第i-1座山的高度低于第i座山的高度，因此，我们也可以改成：max(max(0,a[i-1]-a[i]+1),max(0,a[i-1]-a[i-2]+1)) 贼长）

代码：

 #include<cstdio>

 #include<cstring>

 #include<iostream>

 #include<cmath>

 #include<algorithm>

 using namespace std;

 const int maxn=5e3+,maxe=5e3+,INF=0x3f3f3f3f;

 int n,m,a[maxn],f[maxn][maxn][],ans;

 inline int read(){

     int s=,t=;

     char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')t=-;ch=getchar();}

     while(ch>=''&&ch<='')s=s*+ch-'',ch=getchar();

     return s*t;

 }//朴素快读

 int main(){

     freopen("a.in","r",stdin);

     n=read();

     for(int i=;i<=n;i++)a[i]=read();

     a[]=INF;

     memset(f,0x3f,sizeof(f));

     f[][][]=f[][][]=f[][][]=;//初始化

     for(int i=;i<=n;i++){

         f[i][][]=f[i-][][];

         for(int j=;j<=(i+)/;j++){//这里我测了一下，不管是用floor+1还是用ceil都不行，神奇

             f[i][j][]=min(f[i-][j-][]+max(,a[i-]-a[i]+),f[i-][j-][]+max(max(,a[i-]-a[i]+),max(,a[i-]-a[i-]+)));

             f[i][j][]=min(f[i-][j][],f[i-][j][]+max(,a[i]-a[i-]+));

         }

         //cout<<floor(i/2)+1<<" "<<(i+1)/2<<endl;

     }

     for(int i=;i<=(n+)/;i++)cout<<min(f[n][i][],f[n][i][])<<" ";

     return ;

 }

嘤嘤嘤，溜了