题目是给你n个数,两两之间可以合并,问你最少合并多少次,可以使得序列是递增序列?数据范围是O(N)解决.
我们很容易联想到f[i]表示前i个满足最少需要合并多少次?然后也容易想到一种错误的贪心想法,就是从前往后能不用就不用,选完就好.之所以这种不一定对是因为这种不能最小化代价,代码有hack数据.
考虑f[i],我们可以选的话.(先有一个证明,f[i+1]<=f[i]+1.因为我们可以把i+1个并给第i个.)在有这个证明的基础上,考虑转移的条件(if(sum[i]>=sum[j]+last[j]))在我们选择的时候,假如l<r,且sum[r]+last[r]<=sum[l]+last[l],那么前面一定会淘汰,我们选的时候,选队头的靠后,且满足条件的.如此这题就完成了.
代码如下:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e5+5;
int a[N];
ll f[N],sum[N],q[N],l=1,r,last[N];
int main()
{
    int n;scanf("%d",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%d",&a[i]);
        sum[i]+=sum[i-1]+a[i];
    }
    for(int i=1;i<=n;i++)
    {
        while(l<=r&&(sum[q[l]]+last[q[l]]<=sum[i]))    l++;
        f[i]=f[q[l-1]]+(i-q[l-1]-1);
        last[i]=sum[i]-sum[q[l-1]];
        while(r>=l&&((sum[i]+last[i])-(sum[q[r]]+last[q[r]])<=0))    r--;
        q[++r]=i;
    }printf("%lld\n",f[n]);
    return 0;
}