- it技术
- 修剪草坪（动态规划+单调队列优化）
思路：dp[i]表示前i个奶牛符合条件的最大值是多少，那么可以发现他是由前i-1个合法选第i个时不合法或者是在前i-j-1(0<=j<=k)选出合法奶牛的最大价值然后加上后面i-j——i的奶牛价值dp[i]=max(dp[i-1],dp[i-j-1]+s[i]-s[i-j])因为s[i]是固定的所有可以吧(dp[i-j-1]-s[i-j])看成一起也就是求这个部分的最大那么我们用个单调队列去维护合法区间的最小值（滑动窗口）
#pragma GCC optimize(2)
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
#include<iostream>
#include<vector>
#include<queue>
#include<map>
#include<stack>
#include<iomanip>
#include<cstring>
#include<time.h>
using namespace std
;
typedef long long ll
;
#define SIS std::ios::sync_with_stdio(false)
#define space putchar(' ')
#define enter putchar('\n')
#define lson root<<1
#define rson root<<1|1
typedef pair
<int,int> PII
;
const int mod
=1e9+7;
const int N
=2e6+10;
const int M
=1e3+10;
const int inf
=0x3f3f3f3f;
const int maxx
=2e5+7;
const double eps
=1e-6;
int gcd(int a
,int b
)
{
return b
==0?a
:gcd(b
,a
%b
);
}
ll
lcm(ll a
,ll b
)
{
return a
*(b
/gcd(a
,b
));
}
template <class T>
void read(T
&x
)
{
char c
;
bool op
= 0;
while(c
= getchar(), c
< '0' || c
> '9')
if(c
== '-')
op
= 1;
x
= c
- '0';
while(c
= getchar(), c
>= '0' && c
<= '9')
x
= x
* 10 + c
- '0';
if(op
)
x
= -x
;
}
template <class T>
void write(T x
)
{
if(x
< 0)
x
= -x
, putchar('-');
if(x
>= 10)
write(x
/ 10);
putchar('0' + x
% 10);
}
ll
qsm(int a
,int b
,int p
)
{
ll res
=1%p
;
while(b
)
{
if(b
&1)
res
=res
*a
%p
;
a
=1ll*a
*a
%p
;
b
>>=1;
}
return res
;
}
ll s
[N
];
ll dp
[N
];
int n
,k
;
int q
[N
];
ll
getid(int x
)
{
return dp
[x
-1]-s
[x
];
}
int main()
{
scanf("%d%d",&n
,&k
);
for(int i
=1;i
<=n
;i
++){
scanf("%lld",&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
++;
dp
[i
]=max(dp
[i
-1],getid(q
[hh
])+s
[i
]);
while(hh
<=tt
&&getid(q
[tt
])<=getid(i
)) tt
--;
q
[++tt
]=i
;
}
printf("%lld",dp
[n
]);
return 0;
}
