题目描述
在一年前赢得了小镇的最佳草坪比赛后，FJ变得很懒，再也没有修剪过草坪。现在，新一轮的最佳草坪比赛又开始了，FJ希望能够再次夺冠。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N只排成一排的奶牛，编号为1到N。每只奶牛的效率是不同的，奶牛i的效率为Ei。
靠近的奶牛们很熟悉，如果FJ安排超过K只连续的奶牛，那么这些奶牛就会罢工去开派对。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。
然而，FJ的草坪非常脏乱，因此，FJ只能够让他的奶牛来完成这项工作。FJ有N只排成一排的奶牛，编号为1到N。每只奶牛的效率是不同的，奶牛i的效率为Ei。
靠近的奶牛们很熟悉，如果FJ安排超过K只连续的奶牛，那么这些奶牛就会罢工去开派对。因此，现在FJ需要你的帮助，计算FJ可以得到的最大效率，并且该方案中没有连续的超过K只奶牛。
输入描述:
第一行：空格隔开的两个整数N和K；
第二到N+1行：第i+1行有一个整数Ei。
输出描述:
一行一个值，表示FJ可以得到的最大的效率值。
输入
5 2 1 2 3 4 5
输出
12
说明
FJ有5只奶牛，他们的效率为1,2,3,4,5。他们希望选取效率总和最大的奶牛，但是他不能选取超过2只连续的奶牛。FJ选择出了第三只以外的其他奶牛，总的效率为1+2+4+5=12。
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 7; typedef long long LL; LL a[N], q[N], sum[N], dp[N], n, k; int main() { cin >> n >> k; for (int i = 1; i <= n; i++) cin >> a[i]; for (int i = 1; i <= n; i++) sum[i] = sum[i - 1] + a[i]; int l = 0, r = 0; for (int i = 1; i <= n; i++) { while (i - q[l] > k + 1) l++; dp[i] = dp[q[l]] + a[i]; while (l <= r && dp[q[r]] > dp[i]) r--; q[++r] = i; } LL ans = 1e18; for (int i = n - k; i <= n; i++) ans = min(ans, dp[i]); cout << sum[n] - ans << endl; return 0; }
原文链接: https://www.cnblogs.com/HighLights/p/13330431.html
欢迎关注
微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍;
也有高质量的技术群，里面有嵌入式、搜广推等BAT大佬
原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/367633
非原创文章文中已经注明原地址，如有侵权，联系删除
关注公众号【高性能架构探索】，第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处！
