4462 4.曙曙献爱心

#include<bits/stdc++.h>
using namespace std;
int n,m,k;
int a[1001];
int s[1001];
int f[1001][1001];//f[i][j]，i个警察，j个点，能管理的最大人数 
int main(){cin>>n>>m>>k;for(int i=1;i<=n;i++){cin>>a[i];s[i]=s[i-1]+a[i];//前缀和 }/*for(int i=1;i<=n;i++){cout<<s[i]<<" ";}cout<<endl;*/for(int i=1;i<=m;i++)//f[i][j],i个警察，j个点，能管理的最大人数 {int t=min(i*k,n);//i个警察，最多能管理i*k个集会点，但不能超过n，防止数组越界 for(int j=1;j<=t;j++){f[i][j]=s[j];//cout<<setw(4)<<f[i][j]; }//超过i*k的新集会点，分两种情况//1.新地点不用管；2.新低点需要管（必定一个警察管最后k个点为最优） for(int j=t+1;j<=n;j++){f[i][j]=max(f[i][j-1],f[i-1][j-k]+s[j]-s[j-k]);//cout<<setw(4)<<f[i][j];}//cout<<endl;}cout<<f[m][n];return 0;
}