首页 > 代码库 > 选择数字
选择数字
题目描述
给定一行n个非负整数a[1]..a[n]。现在你可以选择其中若干个数,但不能有超过k个连续的数字被选择。你的任务是使得选出的数字的和最大。
输入输出格式
输入格式:
第一行两个整数n,k
以下n行,每行一个整数表示a[i]。
输出格式:
输出一个值表示答案。
输入输出样例
输入样例#1:
5 2 1 2 3 4 5
输出样例#1:
12
说明
对于20%的数据,n <= 10
对于另外20%的数据, k = 1
对于60%的数据,n <= 1000
对于100%的数据,1 <= n <= 100000,1 <= k <= n,0 <= 数字大小 <= 1,000,000,000
时间限制500ms
动归 设f[i]为取前i件物品的最大价值,因为不能连续取k件,所以f[i]的状态可由j∈[i-k+1,i]转移来。
f[i]=max(f[j]+sum[i]-sum[j+1],f[j-1]+sum[i]-sum[j])
=max(f[j]-sum[j+1],f[j-1]-sum[j])+sum[i]
维护一个单调队列就行了
复杂度O(n)
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<algorithm> 5 using namespace std; 6 int n,k; 7 long long sum[100001],f[100001]; 8 long long q[100001],d[100001]; 9 int head,tail=1; 10 int main() 11 { 12 int i,j; 13 cin>>n>>k; 14 for (i=1; i<=n; i++) 15 { 16 scanf("%lld",&sum[i]); 17 sum[i]+=sum[i-1]; 18 } 19 head=0;tail=1; 20 for (i=1; i<=n; i++) 21 { 22 d[i]=f[i-1]-sum[i]; 23 if (i>=k+1&&d[i-k-1]==q[head]) head++; 24 while (head<tail&&d[i]>q[tail-1]) tail--; 25 q[tail++]=d[i]; 26 f[i]=q[head]+sum[i]; 27 } 28 cout<<f[n]; 29 }
选择数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。