[FROM WOJ]#2214 除虫药水#2214 除虫药水

183 阅读 0 评论 121 点赞

我是靠谱客的博主优秀板栗，这篇文章主要介绍[FROM WOJ]#2214 除虫药水#2214 除虫药水，现在分享给大家，希望可以做个参考。

#2214 除虫药水

传送门

SOL

每瓶高级药水都必须在至多 L 片连续的苹果林中使用

这句话的意思是每瓶高级药水都会对长为 $L$ 的区间产生影响，但是效果不能叠加

设 $f [i] [j]$ 表示前 $i$ 片地用了 $j$ 瓶高级药水的最大值
一个显然的贪心——你有一个高级药水，你一定会用她去尽量覆盖长的区间
容易得到：
$f [i] [j] = m a x (f [i - 1] [j] + a [i + 1], f [i - L] [j - 1] + k * (s [i] - s [i - L]))$

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
#include<bits/stdc++.h>
using namespace std;
#define re register
template<typename T>inline void chmin(T &a,T b){return a<b?a:b;}
template<typename T>inline void chmax(T &a,T b){return a>b?a:b;}
inline char nc(){
    static char buf[10000],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++;
}
inline int rd(){
	int data=0;static char ch=0;
	while(!isdigit(ch=nc()));data=ch^48;
	while(isdigit(ch=nc()))data=(data<<3)+(data<<1)+(ch^48);
	return data;
}
const int N=1005;
int a[N],s[N],f[N][N],n,m,k,l;
int main(){
	n=rd(),m=rd(),k=rd(),l=rd();
	for(int re i=1;i<=n;++i)s[i]=s[i-1]+(a[i]=rd());
	for(int re i=0;i^n;++i){
		for(int re j=0;j<=m;++j){
			f[i+1][j]=max(f[i+1][j],f[i][j]+a[i+1]);
			int re r=min(i+l,n);
			if(j)f[r][j]=max(f[r][j],f[i][j-1]+k*(s[r]-s[i]));
		}
	}printf("%d",f[n][m]);
	return 0;
}