（我上绿了）Hills

纪念一下自己上绿了。

下面是题目：

题意：当一个数满足大于他相邻的数的时候，可以在他这建房子，我们每次操作可以将某个数减1，问最少操作多少次可以满足（1～（n+1）/2)。
思路：
一开始想的是定义状态是f[i][j]表示考虑前i个建立j个房子的最小操作数，后来发现好像不够，因为我们很难判断出第i个第i-1第i-2个数之间的关系，那么我们还是加一维吧，表示第i个数是否建立房子，并且只考虑前i个，不考虑i+1个，那么初始化的时候把所有建房子的数量为0的方案数的步数变为0，f[1][1][1]也变成0，状态转移方程：
第i个数不建立房子的方程很好说，
f[i][j][0]=min(f[i-1][j][1]+max(0,a[i]-a[i-1]+1),f[i-1][j][0]);只需要看他前一个房子是否建立，不建立就啥也不动，建立的话就要减少到前一个房子-1
第i个数如果建立房子就要分类讨论了。第i个建立那么第i-1的地方一定不能建立，所以肯定是由f[i-1][j-1][0]转移过来的，接下来我们要找到f[i-1][j-1][0]的前驱，前驱如果是i-2 1的话，也就是i-2的位置建立房子，那么我们减去i-1
之前减去的长度，然后将i-1减到满足比i-2小并且比i小的最大高度。反之，如果i-2没有建立房子，那么我们只需要满足i-1的位置比i低就行了。
代码：

#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
using namespace std;
const int N=5010;
int n;
int a[N];
int f[N][N/2][2];	//只考虑前i个并且第i个（建或者不建）已经建了j个房子的最小操作数
int main()
{
	memset(f,0x3f,sizeof f);
	cin>>n;
	for(int i=1;i<=n;i++)
	cin>>a[i];
	for(int i=0;i<=n;i++)
		f[i][0][0]=0;
		f[1][1][1]=0;
	for(int i=2;i<=n;i++)
	{
		for(int j=1;j<=(1+i)/2;j++)
			{
				f[i][j][0]=min(f[i-1][j][1]+max(0,a[i]-a[i-1]+1),f[i-1][j][0]);
				if(f[i-1][j-1][0]==f[i-2][j-1][1]+max(0,a[i-1]-a[i-2]+1))
				{
					f[i][j][1]=min(f[i][j][1],f[i-1][j-1][0]-max(0,a[i-1]-a[i-2]+1)+max(0,max(a[i-1]-a[i-2]+1,a[i-1]-a[i]+1)));
				}
				else
					f[i][j][1]=min(f[i-1][j-1][0]+max(0,a[i-1]-a[i]+1),f[i][j][1]);
			}

	}
	for(int i=1;i<=(1+n)/2;i++)
		cout<<min(f[n][i][0],f[n][i][1])<<' ';
		cout<<endl;
	return 0;
}

本文地址：https://blog.csdn.net/qq_45961321/article/details/108571767