题解 P2300 【合并神犇】

· · 题解

听说这题可以n^2水过去，

不过这里介绍一种O(n)的做法。

$pre[i]$为第$[1,i]$位最末尾的数 $j$为满足$sum[i]-sum[j]>=pre[j]$的最大数 $f[i]=f[j]+i-j-1 pre[i]=sum[i]-sum[j]

显然pre[i]越小越好，这样找到一个就可以退出。

所以可以直接用单调队列优化。

时间复杂度O(n)。

代码，注意开\texttt{long~long}：

#include <bits/stdc++.h>
using namespace std;
typedef int _int;
#define int long long

const int N=200010;
int head,tail=1;
int n,f[N],pre[N],sum[N],q[N];

_int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    int x;
    for (int i=1;i<=n;++i)
        cin>>x,sum[i]=sum[i-1]+x;
    for (int i=1;i<=n;++i) {
        while (head+1<tail&&sum[i]>=sum[q[head+1]]+pre[q[head+1]])
            ++head;
        f[i]=f[q[head]]+1;
        pre[i]=sum[i]-sum[q[head]];
        while (head<tail&&sum[q[tail-1]]+pre[q[tail-1]]>sum[i]+pre[i])
            --tail;
        q[tail++]=i;
    }
    cout<<n-f[n];
    return 0;
}