本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2022-11-07 14:53:33

\/*
dp[i][j][0\/1\/2]，表示前i个山，建j个房子，
	0:i和i-1都不建，....
	1:i建， (i-1,i)\/
	2:i-1建时最小花费。(i-1,i)\
	
	每种专业都由上一行转移而来，可以滚动优化 
*\/
#include<bits\/stdc++.h>
using namespace std;
const int N=5009;
int dp[2][N][3],a[N<<1];
int main(){
  int n;
  cin>>n;
  for(int i=1;i<=n;i++)
      cin>>a[i];
  memset(dp,0x3f,sizeof(dp));
  dp[1][0][0]=dp[1][1][1]=0;
  for(int i=2;i<=n;i++){
  	for(int j=0;j<=(i+1)\/2;j++){
          dp[i&1][j][0]=min(dp[(i-1)&1][j][0],dp[(i-1)&1][j][2]);\/\/i和i-1都没房子，i-2和i-1没有房子，或者 i-1前面有房子 
          dp[i&1][j][2]=dp[(i-1)&1][j][1]+max(0,a[i]-a[i-1]+1);\/\/i-1处有房子，处理房子右侧左侧下降部分的修改值 \/
          dp[i&1][j][1]=min(dp[(i-1)&1][j-1][0]+max(0,a[i-1]-a[i]+1),dp[(i-1)&1][j-1][2]+max(0,min(a[i-1],a[i-2]-1)-a[i]+1));
      \/\/i建房子：        i-2，i-1没有房子，只根据自己修改左侧i-1，              i-2处有房子  ，根据i-2和i修改i-1 
	  }
	 memset(dp[(i-1)&1],0x3f,12*n+12) ;
  }