前言
思路
集合表示 : $f[i]$ 表示从前$i$头牛,并且合法的最大价值
对于当前第$i$头牛来考虑 :
- 不选,那么可以直接从$f[i-1]$转移过来
- 选, 那么肯定不能连续选,所以我们将$i$前面分为几个小段
$[i-j+1,i],[i-j+2,i].....$
因此状态计算为 :
$f[i] = max(f[i-1],f[i-j-1]+s[i] - s[i-j])$
我们可以将右边化简为 :
$f[i-j-1] - s[i-j] +s[i] = g(i-j)+s[i]$
为了使价值最大我们应该使得$max(g(i-j))$ 因此我们可以使用一个滑动窗口
维护一个长度为$k$区间的最大值
code
const int N = 1e5+10;
ll f[N],s[N];
int q[N],a[N];
ll g(int i){
if(i == 0)
return 0;
return f[i-1] - s[i];
}
void solve()
{
int n,k;cin>>n>>k;
for(int i=1;i<=n;i++){
cin>>a[i];
s[i] = s[i-1]+a[i];
}
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]<<endl;
}
/**mYHeart is my algorithm**/
int main()
{
//int t;cin>>t;while(t -- )
solve();
return 0;
}