二刷提高课,题解目录在这里— 提高课的题解目录
注意这里的状态表示f[i]意为1~i合法且选择了i
注意做的目的是一来后面好用单调队列优化来写,而不去考虑第i太选还是不选
二来我们发现即使如果i台不选与前与后均有关系,所以不再去考虑
所以我们输出答案的时候也需要遍历一下后面m个到底是哪个最小
#include<iostream>
using namespace std;
const int N=2e5+10;
int f[N];
int v[N];
int q[N];
int n,m;
int main()
{
cin>>n>>m;
for(int i=1;i<=n;i++)cin>>v[i];
int hh=0,tt=0;
for(int i=1;i<=n;i++)
{
while(hh<=tt&&i-q[hh]>m)hh++;
f[i]=f[q[hh]]+v[i];
while(hh<=tt&&f[q[tt]]>=f[i])tt--;
q[++tt]=i;
}
int res=1e9;
for(int i=n-m+1;i<=n;i++)res=min(res,f[i]);
cout<<res;
return 0;
}