Towers CodeForces - 229D（每日DP)*

题意：给你一排的塔，可以一座塔可以叠在他的左边和右边。，求变成LCS的最小操作。

一开始看到数据以为要O(N)好吧其实5000可以On。。。
其他塔向左还是向右这没区别
我们用dp[i]来表示到这个塔的最小操作，每次操作是一个区间需要的次数就是i-j-1这下直接两个for可以了。但是有一个情况是操作后塔高要如何处理= =，然鹅有些题解直接开了一个数组存放最小的塔高（解锁新操作），就这样直接搞满足区间累加高度本来高度以及操作后的最小塔高就可以了。

#include<bits/stdc++.h>
using namespace std;
const int maxn=3e5+10;
int sum[maxn];
int a[maxn];
int dp[maxn];
char str[maxn];
int h[maxn];
int main()
{
    int n;
    cin>>n;
    memset(h,0x3f,sizeof h);
    memset(dp,0x3f,sizeof dp);
    h[0]=dp[0]=0;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }

    for(int i=1;i<=n;i++){
        for(int j=0;j<i;j++){
            if(sum[i]-sum[j]>=a[j]&&sum[i]-sum[j]>=h[j]){
                dp[i]=min(dp[i],dp[j]+i-j-1);
                if(sum[i]-sum[j]<=h[i]){
                    h[i]=sum[i]-sum[j];
                }
            }
        }
    }
    cout<<dp[n]<<endl;
}