选择数字

题目描述

给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数，但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。

输入格式

第一行两个整数n，k。

以下n行，每行一个整数表示a[i]。

输出格式

输出一个值表示答案。

输入输出样例

输入

5 2
1
2
3
4
5 

输出

12

说明/提示

对于20%的数据，n <= 10。

对于另外20%的数据， k = 1。

对于60%的数据，n <= 1000。

对于100%的数据，1 <= n <= 100000，1 <= k <= n，0 <= 数字大小 <= 1,000,000,000。

时间限制500ms。

数组含义

a[i]: 原数组。

sum[i]: 前缀和，便于计算。

dp[i][1/0]: 前i个数字的状态下，第i个数字选/不选的和的最大值。

q[i]: 在单调数列中第i个数字，在原数组的下标。

基本思路

当第i个数字不选的时候，比较简单，取前i-1的状态选或不选的最大值即可。

dp[i][0]=max(dp[i-1][0],dp[i-1][1])

当第i个数字选的时候，可以枚举前j个数字的状态，依次取最大值即可。

dp[i][1]=max(dp[j][0])-sum[j]+sum[i]（伪代码，误抄）

但是本题数据很大，暴力枚举j，效率堪忧。

因为题中可以对a[i]选或不选，在有限制的条件下，a[i]肯定越大越好，所以可以用到单调队列进行优化。

（在此提一句，刚开始我想到用贪心，从头枚举，每个区间都正好卡‘k‘的长度，但是很明显可以举出反例）

7 3
1 4 1 10000 1 4 1

用到单调队列，就可以把式子改了。

dp[i][1]=dp[q[head]][0]-sum[q[head]]+sum[i]

最后记得开long long哟。

代码

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

const int maxn=1e6+50;
int n,k;
ll a[maxn];
ll sum[maxn];
ll dp[maxn][2];
ll q[maxn];

int main(){
    int head=1;
    int tail=1;//这个我测试了一下，必须是1，若为0，则需要进行初始化
    cin>>n>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i];
    }
    dp[1][1]=a[1];//tail=0时必加的初始化
    for(int i=1;i<=n;i++){
        dp[i][0]=max(dp[i-1][0],dp[i-1][1]);
        while(q[head]<i-k&&head<=tail){//去掉最先走出队列，而且值也不大的数字
            head++;
        }
        dp[i][1]=dp[q[head]][0]-sum[q[head]]+sum[i];
        while(sum[i]-dp[i][0]<sum[q[tail]]-dp[q[tail]][0]&&head<=tail){//若尾端加入的数字，去掉的数字总值比i时还大，则直接去掉
            tail--;
        }
        q[++tail]=i;
    }
    printf("%lld\n",max(dp[n][1],dp[n][0]));
    return 0;
}

P2034 选择数字——线性dp（单调队列优化）

原文：https://www.cnblogs.com/Rubyonly233/p/13197344.html