选取数对

给定一个长度为 n 的整数数列 a1,a2,…,an。

请你选择 k 个数对 [l1,r1],[l2,r2],…,[lk,rk]，要求所选数对满足：

1. 1≤l~1~≤r~1~<l~2~≤r~2~<…<l~k~≤r~k~≤n。
2. 对于 1≤i≤k，ri−li+1=m 均成立。

请你输出 sum 的最大可能值。

输入格式

第一行包含三个整数 n,m,k。

第二行包含 n 个整数 a1,a2,…,an。

输出格式

一个整数，表示 sum 的最大可能值。

数据范围

前 6 个测试点满足 1≤m×k≤n≤20。
所有测试点满足 1≤m×k≤n≤5000，0≤a~i~≤10^9^。

输入样例1：

5 2 1
1 2 3 4 5

输出样例1：

9

输入样例2：

7 1 3
2 10 7 18 5 33 0

输出样例2：

61

思路

闫式dp分析法
状态表示f[i][j]:表示在前i个数中选，j个区间的所有集合,属性:max
状态计算f[i][j]:根据最后一个区间是否包含最后一个点i来进行集合划分
1.不包含:f[i][j]=max(f[i][j],f[i-1][j])
2.包含:f[i][j]=max(f[i][j],f[i-m][j-1]+sum[i]-sum[i-m]) //如果包含i的话最后一个区间的右端点就是i

代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

const int N=5010;
typedef long long LL;
int a[N];
LL sum[N];
LL f[N][N];
int n,m,k;

int main(){
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        sum[i]=sum[i-1]+a[i]; //前缀和
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            f[i][j]=f[i-1][j];
            if(i-m+1>=1){
                LL num=f[i-m][j-1]+sum[i]-sum[i-m];
                f[i][j]=max(f[i][j],num);   
            }
        }
    }
    cout<<f[n][k]<<endl;
    return 0;
}