首页 > 代码库 > 【COGS1384】鱼儿仪仗队

【COGS1384】鱼儿仪仗队

2024-07-05 12:03:24   223人阅读

【题目描述】

Jzyz的池塘里有很多条鱼，鱼儿们现在决定组成一个仪仗队。现在备选的N(1 <= N <= 100,000)条鱼排成了一条直线，并且按照亲近关系排的队伍，鱼儿的顺序不能改变，现在知道每条鱼的魅力值是Xi(0 <=Xi <= 1,000,000,000)。

挑选仪仗队的任务交给了小x手里（小x并不是鱼），小x发现，如果连续的挑选超过K条鱼，那么这些鱼因为关系太好，结成小团队，影响仪仗队的团结。

所以，小x挑选仪仗队的唯一原则是不能连续挑选超过K条鱼，现在小x想知道，组成仪仗队的鱼儿的最大的魅力值之和是多少。

【输入格式】

第一行：两个整数N和K

接下来N行，每行一个整数Xi，表示第i条鱼的魅力值。

【输出格式】

一个整数，表示仪仗队最大的魅力值之和。

【分析】

一道简单的单调队列，不解释了。

 1 #include <iostream>
 2 #include <cstring>
 3 #include <cstdlib>
 4 #include <cmath>
 5 #include <cstdio>
 6 const int maxn=100010;
 7 using namespace std;
 8 long long Q[maxn],shu[maxn];
 9 long long f[maxn],n,k;
10 int main()
11 {
12     long long i,lj=0;
13         memset(f,0,sizeof(f));
14     
15     scanf("%lld%lld",&n,&k);
16     for (i=1;i<=n;i++) {scanf("%lld",&shu[i]);lj+=shu[i];}
17     int front=1,rear=1;
18     for (i=1;i<=(n+1);i++)
19     {
20         while (front<rear && (i-Q[front]-1)>k) front++;
21         if (i-1<=k) f[i]=min(shu[i],f[Q[front]]+shu[i]);
22         else f[i]=f[Q[front]]+shu[i];
23         while (front<rear && f[i]<f[Q[rear]]) rear--;
24         Q[++rear]=i;
25     }
26     printf("%lld",lj-f[n+1]);
27     return 0;
28 }
View Code

 


联系
我们