洛谷P2627 修剪草坪

@Pelom  September 26, 2019

题意

从数列$a$中选出若干数,但不能有超过$k$个连续的数字被选择,求选出数字的最大和

数据范围:$1 \le n \le 10^5,1 \le a_i \le 10^9$

题解

用$f[i]$表示选到第$i$个时的最大值,显然,在$j \in [i-k,i]$一定存在至少$1$个断点,否则存在超过$k$的连续段,所以枚举该断点
$$f[i]=max(f[j-1]+a[j+1]+ \dots +a[i])$$
将求和部分用前缀和优化
$$f[i]=max(f[j-1]+s[i]-s[j])$$
可将$s[i]$移出
$$f[i]=max(f[j-1]-s[j])+s[i]$$
此时取最大值只与$j$有关,考虑单调队列优化

代码:

#include<iostream>
#include<cstdio>
using namespace std;
#define int long long
const int N=100000+10;
int n,r;
int a[N],s[N],b[N],q[N];
int frt,bck=1;
int dp[N];
signed main(){
    scanf("%lld%lld",&n,&r);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        s[i]=s[i-1]+a[i];
    }
    for(int i=1;i<=n;i++){
        b[i]=dp[i-1]-s[i];
        for(;b[q[bck]]<b[i] && bck>=frt;bck--);
        q[++bck]=i;
        for(;i-q[frt]>r && bck>=frt;frt++);
        dp[i]=b[q[frt]]+s[i];
    }
    printf("%lld",dp[n]);
    return 0;
}

添加新评论