题目描述

blablabla

样例

blablabla

(单调队列优化) $O(n)$

blablabla

参考文献

参照whsstory大佬的题解

C++ 代码

#include <iostream>
#include <algorithm>
using namespace std;
const int N=100010;
int w[N],f[N],q[N],last[N],s[N];
int main(){
    int n;
    cin>>n;
    for(int i=n;i>=1;--i) cin>>w[i];
    for(int i=1;i<=n;++i){
        s[i]=s[i-1]+w[i];
    }
    int hh=0,tt=0;
    q[tt++]=0;
    for(int i=1;i<=n;++i){
        while(hh!=tt&&last[q[hh]]+s[q[hh]]<=s[i]) hh++;
        last[i]=s[i]-s[q[hh-1]];
        f[i]=f[q[hh-1]]+1;
        while(hh!=tt&&last[q[tt-1]]+s[q[tt-1]]>=s[i]+last[i]) tt--;
        q[tt++]=i;
    }
    cout<<f[n]<<endl;
    return 0;
}