除虫药水（简单dp）

在十年前，除虫是十分艰苦的工作。那时，使用普通药水进行除虫的效果极差，在一片苹果 林中使用后除掉的虫仅为极小一部分。
比如说，Bugs 镇共有 N 片苹果林，对第i 片使用普通药水可以除掉 ai 吨虫。xxx的任务是对这 N 片苹果林中的每一片进行除虫，并且他必 须按照 1 到 N 的顺序依次处理。 xxx另有一种高级药水，其除虫能力为普通药水的 K 倍， 也就是说，在第i 片苹果林中使用高级药水可以除掉 Kai 吨虫。但是，高级药水是极为珍贵 的，xxx 仅有 M 瓶。并且，由于其挥发性极强，每瓶高级药水都必须在至多 L 片连续的 苹果林中使用。现在 xxx 想知道他最多能杀多少吨虫。
输入
第一行四个整数 N, M , K, L 。
第二行 N 个整数，为 ai 。
输出
输出一行一个整数表示答案。
样例输入
5 5 5 5
1 2 3 4 5
样例输出
75
提示
对于 20%的数据， N <=10 。
对于 100%的数据，1<=N, M , L<=1000,1< K< 100,0 <= ai <=1000。

一道简单的dp，dp[i][j]表示在前i片树林中用了j瓶强力药剂的最优值

则有两种可能

1、不使用强力药剂

$dp[i+1][j]=max(dp[i][j]+a[i+1],dp[i+1][j]);$

2、使用了强力药剂
int t=min(n,i+l);
$dp[t][j]=max(dp[i][j-1]+(sum[t]-sum[i])*k,dp[t][j]);$

然后就很简单了

#include<bits/stdc++.h>
using namespace std;
int dp[1006][1005],n,m,k,l,a[1005],sum[1005];
inline short read(){
    char ch=getchar();
    short res=0;
    while(!isdigit(ch)) ch=getchar();
    while(isdigit(ch)) res=(res<<3)+(res<<1)+(ch^48),ch=getchar();
    return res;
}
int main(){
    n=read(),m=read(),k=read(),l=read();
    for(register int i=1;i<=n;i++)
    {
        a[i]=read();
    }
    for(register int i=1;i<=n;i++)
    {
        sum[i]=sum[i-1]+a[i];
    }
    for(register int j=0;j<=m;j++)
    {
        for(register int i=0;i<n;i++)
        {
            dp[i+1][j]=max(dp[i][j]+a[i+1],dp[i+1][j]);
            if(j!=0){
                int t=min(n,i+l);
                dp[t][j]=max(dp[i][j-1]+(sum[t]-sum[i])*k,dp[t][j]);
            }
        }
    }
    printf("%d",dp[n][m]);
    return 0;
}