题目链接：https://ac.nowcoder.com/acm/contest/2652/G
题目大意：与上一篇博客 烽火传递 差不多。
1.一共n头羊，若超过m头连续的羊在一起，就会集体罢工，每头羊有一个工作效率，求如何选择羊使得工作效率最高
题解思路：
1.我们可以转换思路，首先选择全部的羊，然后这是集体罢工，我们去拆分他们，即转换成了每连续的 m + 1头羊之间必须拆掉一头羊，则作为效率损失。
2.dp[i] 表示 拆掉第 i 只羊所造成的最小总损失。于是与烽火传递一样了。
3.该题还有一个注意的点是效率是1e9范围内，我们的inf不能开0x3f3f3f3f，不够大，需开 1ll << 62。
代码如下：
#include<stdio.h>
#include<deque>
#include<algorithm>
typedef long long ll;
const int MAXN = 1e5 + ;
using namespace std;
const ll inf = 1ll << ; int n, m;
ll a[MAXN];
ll dp[MAXN]; //表示第 i 个烽火台放置烽火时的最小总代价
deque<int> Q; int main()
{
ll sum = ;
scanf("%d%d",&n, &m);
m ++;
for(int i = ; i <= n; i ++)
{
scanf("%lld", &a[i]);
sum += a[i];
}
for(int i = ; i <= m; i ++)
{
dp[i] = a[i];
while(!Q.empty())
{
if(dp[i] < dp[Q.back()])
Q.pop_back();
else
break;
}
Q.push_back(i);
}
for(int i = m + ; i <= n; i ++)
{
while(!Q.empty())
{
if(i - m > Q.front())
Q.pop_front();
else
break;
}
dp[i] = dp[Q.front()] + a[i];
while(!Q.empty())
{
if(dp[i] < dp[Q.back()])
Q.pop_back();
else
break;
}
Q.push_back(i);
} ll minn = inf;
for(int i = n; i > n - m; i --)
minn = min(minn, dp[i]);
printf("%lld\n", sum - minn);
return ;
}
/*
5 3
1 2 5 6 2 4
*/