P2034 选择数字——线性dp(单调队列优化)

时间:2022-11-17 21:36:06

选择数字

题目描述

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

输入格式

第一行两个整数 \(n\),\(k\) 。

以下 \(n\) 行,每行一个整数表示 \(a[i]\) 。

输出格式

输出一个值表示答案。

输入输出样例

输入

5 2
1
2
3
4
5

输出

12

说明/提示

对于 \(20\%\) 的数据,\(n\leq 10\) 。

对于另外 \(20\%\) 的数据,\(k=1\) 。

对于 \(60\%\) 的数据,\(n\leq 1000\) 。

对于 \(100\%\) 的数据,\(1\leq n\leq 100000\),\(1\leq k\leq n\),\(0\leq 数字大小\leq 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;
}