题目:
在一年前赢得了小镇的最佳草坪比赛后,FJ 变得很懒,再也没有修剪过草坪。现在,新一轮的最佳草坪比赛又开始了,FJ 希望能够再次夺冠。
然而,FJ 的草坪非常脏乱,因此,FJ 只能够让他的奶牛来完成这项工作。FJ 有 N 只排成一排的奶牛,编号为 1 到 N。每只奶牛的效率是不同的,奶牛 i 的效率为 Ei 。
靠近的奶牛们很熟悉,如果 FJ 安排超过 K 只连续的奶牛,那么这些奶牛就会罢工去开派对。因此,现在 FJ 需要你的帮助,计算 FJ 可以得到的最大效率,并且该方案中没有连续的超过 K 只奶牛。
思路:
状态表示:
f
[
i
]
f[i]
f[i]表示从前i
个里面选,满足条件的最大效率
状态转移方程:
f
[
i
]
=
m
a
x
(
f
[
i
−
1
]
,
f
[
i
−
j
−
1
]
+
s
[
i
]
−
s
[
i
−
j
]
)
,
1
≤
j
≤
k
f[i] = max(f[i-1],f[i-j-1]+s[i]-s[i-j]),1 \leq j \leq k
f[i]=max(f[i−1],f[i−j−1]+s[i]−s[i−j]),1≤j≤k
不选第i
个对应
f
[
i
−
1
]
f[i-1]
f[i−1],选第i
个对应
f
[
i
−
j
−
1
]
+
s
[
i
]
−
s
[
i
−
j
]
f[i-j-1]+s[i]-s[i-j]
f[i−j−1]+s[i]−s[i−j]
s
[
i
]
s[i]
s[i]固定,而
f
[
i
−
j
−
1
]
−
s
[
i
−
j
]
f[i-j-1]-s[i-j]
f[i−j−1]−s[i−j]的最大值可以使用单调队列进行优化,注意开long long
注意:使用单调队列需要进行初始化
代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 1e5+5;
ll s[N];
ll f[N],q[N];
int n,k;
ll g(int i)
{
return f[i-1] - s[i];
}
int main()
{
cin>>n>>k;
for(int i=1;i<=n;i++)
{
cin>>s[i];
s[i] += s[i-1];
}
int hh=0,tt=0;
for(int i=1;i<=n;i++)
{
if(q[hh] < i-k) hh++;
f[i] = max(f[i-1],g(q[hh])+s[i]);
while(hh<=tt && g(q[tt]) <= g(i)) tt--;
q[++tt] = i;
}
cout<<f[n]<<'\n';
return 0;
}