CF229D Towers

题意是：每次操作能将某个数加到隔壁的数上面，最后求最少操作数，使得序列是非递减序列。
思路：我们发现每次可以将l～r之间的区间合并成一个数，然后需要r-l次操作，我们设定从f[i]为从1处理到i并且序列是递增的最少操作数，然后枚举i是在哪一段区间里，维护l[i]（在不影响f[i]最优值的情况下l[i]最小的可能高度）因为小的高度容易让后面接嘛。
代码：

#include<iostream>
#include<cstring>
using namespace std;
const int N=5010;
#define debug() cout<<"---"<<endl;
int h[N];
int n;
int f[N];//考虑前i个塔的最小操作数 
int minv[N];
int s[N];
int main()
{
   
	cin >> n;
	for(int i=1;i<=n;i++)
		cin>>h[i];
	memset(f,0x3f,sizeof f);
	memset(minv,0x3f,sizeof minv);
	for(int i=1;i<=n;i++)
		s[i]=s[i-1]+h[i];
	f[1]=0;
	f[0]=0;
	minv[0]=0;
	minv[1]=h[1];
	for(int i=2;i<=n;i++)
	{
   
		for(int j=1;j<=i;j++)
			if(s[i]-s[j-1]>=minv[j-1] && f[i]>=f[j-1]+(i-j))//将i～j合并
				{
   
					f[i]=f[j-1]+i-j;
					minv[i]=min(minv[i],s[i]-s[j-1]);
				}
	}
	cout<<f[n]<<endl;
	return 0;
}