题目描述 Description
给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数,但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。
输入描述 Input Description
第一行两个整数n,k
以下n行,每行一个整数表示a[i]。
输出描述 Output Description
输出一个值表示答案。
样例输入 Sample Input
5 2
1
2
3
4
5
样例输出 Sample Output
12
数据范围及提示 Data Size & Hint
对于20%的数据,n <= 10
对于另外20%的数据, k = 1
对于60%的数据,n <= 1000
对于100%的数据,1 <= n <= 100000,1 <= k <= n,
0 <= 数字大小 <= 1,000,000,000
/*
设f[i]为取前i件物品的最大价值,因为不能连续取k件,所以f[i]的状态可由j∈[i-k+1,i]转移来。直接写暴力的DP会超时,由于i的状态与i-k及之前的没有关系了,所以可以用单调队列优化。
*/
#include<cstdio>
#include<iostream>
#define M 100010
#define ll long long
using namespace std;
ll sum[M],f[M],d[M],q[M];
int n,k,head=,tail=;
void put(int j)
{
d[j]=f[j-]-sum[j];
if(j>=k+&&d[j-k-]==q[head])head++;
while(head<tail&&d[j]>q[tail-])tail--;
q[tail++]=d[j];
}
int main()
{
scanf("%d%d",&n,&k);
for(int i=;i<=n;i++)
{
ll x;cin>>x;
sum[i]=sum[i-]+x;
}
for(int i=;i<=n;i++)
{
put(i);
f[i]=q[head]+sum[i];
}
cout<<f[n];
return ;
}