首页 > 代码库 > codevs3327选择数字（单调队列优化）
codevs3327选择数字（单调队列优化）
3327 选择数字
时间限制: 1 s
空间限制: 256000 KB
题目等级 : 钻石 Diamond
题目描述 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
90分代码（其实数据弱，能A的，只是我太弱2333）：
/* f[i]表示前i个数选k个的最大值因为不能连续k个选，所以枚举一下断点 但这个题貌似是个单调队列优化......嗯，，，那就学吧先上个暴力dp */ #include<iostream>#include<cstdio>#define maxn 10000001using namespace std;int n,m,k;int f[maxn],s[maxn],a[maxn];int main(){ scanf("%d%d",&n,&k); for(int i=1;i<=n;i++) { scanf("%d",&a[i]); s[i]=s[i-1]+a[i]; } for(int i=1;i<k;i++) f[i]=s[i]; for(int i=k;i<=n;i++) for(int j=i-k;j<=i;j++) { f[i]=max(f[i],f[j-1]+s[i]-s[j]); } printf("%d\n",f[n]);}
单调队列优化：
/* 考虑从第一位开始递推处理 在第i位的时候，需要在i-k位（取i-k+1到i）到i（不取i）中找一个点不取 设这个点为j，这一段连续的就是j+1到i 那么f[i] = max{f[j-1] + sum[j+1, i]} (i-k<=j<=i) 运用前缀和简化一下就是f[i] = max{f[j-1]-sum[j]+sum[i]}+f[i]; 发现max里面的值只与j有关，所以可以用单调队列优化转移。*/ #include<iostream>#include<cstdio>#define LL long long#define maxn 100010using namespace std;LL n,k,a[maxn],s[maxn],f[maxn];LL head,tail=1,d[maxn],q[maxn];LL que(LL j){ d[j]=f[j-1]-s[j]; while(head<=tail&&d[q[tail]]<d[j]) tail--; q[++tail]=j; while(head<=tail&&q[head]<j-k) head++; return d[q[head]];}int main(){ scanf("%lld%lld",&n,&k); for(LL i=1;i<=n;i++) scanf("%lld",&a[i]),s[i]=s[i-1]+a[i]; for(LL i=1;i<=n;i++) { LL t=-10000000000; f[i]=que(i)+s[i]; } cout<<f[n]; return 0;}
codevs3327选择数字（单调队列优化）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。