codeforces 467C George and Job（简单dp,看了题解抄一遍）

题目

参考了网页：http://www.xue163.com/exploit/180/1802901.html

//看了题解，抄了一遍，眼熟一下，增加一点熟练度
//dp[i][j]表示是前i个数选出j段的最大值，
//显然有不选这个数，和考虑这个数的两种情况。
//而考虑这个数的话，因为连续性也只会增加以这个数为结尾的m序列
#include<stdio.h>
#include<string.h>
#include<algorithm>
using namespace std;
__int64 dp[5010][5010];
int main()
{
    int n,m,k;
    __int64 a,sum[5010];
    memset(sum,0,sizeof(sum));
    scanf("%d%d%d",&n,&m,&k);
    for(int i=1;i<=n;i++){
        scanf("%I64d",&a);
        sum[i]=sum[i-1]+a;
    }
    memset(dp,0,sizeof(dp));
    for(int i=m;i<=n;i++){//for(int i=1;i<=n;i++){ //不可以啊，因为会下标越界？——sum[i-m]
        for(int j=k;j>=1;j--){
            dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m]);
        }
    }
    printf("%I64d
",dp[n][k]);
    return 0;
}