codeforce#dp专项

1 https://codeforces.com/problemset/problem/467/C

【题意】给定一个长度为n的序列，找到k个长度为m的子串（不是子序列），求能得到的每个子串相加后的最大值。特别，子串下标不能重复且不能交叉 。
i i i 表示下标
j j j 表示子串个数
不新增子串，那最大值与上一次的状态相同；
新增子串，那最大值为以当前下标 i i i 结尾的 [ i m + 1 , i ] [i-m+1,i] [im+1,i] 长度的子串，自然 d p [ i m ] [ j 1 ] dp[i-m][j-1] dp[im][j1]为不增加这个子串的最大值，然后再用前缀和加上该区间的值。
两种情况比较取最大（注意第二种情况 i i i 的取值范围）
d p [ i ] [ j ] = m a x ( d p [ i 1 ] [ j ] , d p [ i m ] [ j 1 ] + b [ i ] b [ i m ] dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]-b[i-m] dp[i][j]=max(dp[i1][j],dp[im][j1]+b[i]b[im]

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=5050;
ll a[N],b[N];
ll dp[N][N];
int main(){
    int n,m,k;
    cin>>n>>m>>k;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        b[i]=b[i-1]+a[i];
    }
    int cnt=0;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=k;j++){
            if(i-m>=0){
                dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+b[i]-b[i-m]);
            }
            else dp[i][j]=dp[i-1][j];
        }
    }
    cout<<dp[n][k]<<endl;
    return 0;
}