Codeforces 1013E Hills

题面在这里

题意：长度为n的高度序列，房子只能造在比相邻位置高的地方，可以花费1的代价将任意位置高度-1，问造\(k(k=1\dots \lceil \frac n 2 \rceil)\)座房子的最小代价

​

定义\(f_{i,j,0/1}\)表示前i个位置，造了j个房子，第i个位置有没有造房子

然后就好了

​

示例程序：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define cl(x,y) memset(x,y,sizeof(x))
using namespace std;

const int maxn=5005;
int n,a[maxn],f[maxn][maxn][2];
inline int w(int x,int y){
	return max(0,x-y);
}
int main(){
	scanf("%d",&n);
	for (int i=1;i<=n;i++) scanf("%d",&a[i]);
	cl(f,63);
	f[0][0][0]=0;
	for (int i=1;i<=n;i++)
	 for (int j=0;j<=i;j++){
	 	f[i][j][0]=min(f[i-1][j][0],f[i-1][j][1]);
	 	if (i==1&&j>0) f[i][j][1]=w(a[i+1],a[i]-1);
	 	if (i>1&&j>0) f[i][j][1]=min(f[i-2][j-1][0]+w(a[i-1],a[i]-1),f[i-2][j-1][1]+w(min(a[i-2]-1,a[i-1]),a[i]-1))+w(a[i+1],a[i]-1);
	 }
	for (int i=1;i<=(n+1)/2;i++) printf("%d ",min(f[n][i][0],f[n][i][1]));
	return 0;
}