首页 > 代码库 > 选择数字（codevs 3327）
选择数字（codevs 3327）
题目描述 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 longusing namespace std;ll sum[M],f[M],d[M],q[M];int n,k,head=0,tail=1;void put(int j){ d[j]=f[j-1]-sum[j]; if(j>=k+1&&d[j-k-1]==q[head])head++; while(head<tail&&d[j]>q[tail-1])tail--; q[tail++]=d[j];}int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { ll x;cin>>x; sum[i]=sum[i-1]+x; } for(int i=1;i<=n;i++) { put(i); f[i]=q[head]+sum[i]; } cout<<f[n]; return 0;}
选择数字（codevs 3327）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。