zcmimi's blog
查看原题

点击跳转

单调队列优化dp

f[i]表示从1-i最多能选出的效率

枚举断点j,

f[i] = \max(f[j-1]+ \sum_{t=j+1}^i a[t])

但是直接这样的复杂度不可行

我们可以考虑用单调队列优化

f[i] = \max(f[j-1] - S_j) + S_i

#include<iostream>
#include<cstdio>
using namespace std;
#define ll long long
ll n,m,a[100010],sum[100010],f[100010];
ll d[100010];
int q[100010],head=0,tail=1;
ll que(int i){
    d[i]=f[i-1]-sum[i];
    while(head<=tail&&d[q[tail]]<d[i])tail--;
    q[++tail]=i;
    while(head<=tail&&q[head]<i-m)head++;
    return d[q[head]];
}
int main(){
    scanf("%lld%lld",&n,&m);
    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)f[i]=que(i)+sum[i];
    cout<<f[n];
}
LG 2627 修剪草坪
comment评论
Search
search