1 /* 2     题意：给一个长度为n的序列， 从中选择长度为m的k个区间（任意两个区间不会有公共部分） 3     使得所选择的区间的和最大！ 4     思路：这是一种很常见的dp 5      6     dp[i][j] 表示的是前 i 个数选择 j 个 长度为m区间的最大和！  7     s[i]记录的是前 i 个数字的和！  8     dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] ); 9 */10 #include<iostream>11 #include<cstdio>12 #include<cstring>13 #include<algorithm>14 #define N 500515 using namespace std;16 typedef long long ll;17 18 ll dp[N][N];19 ll s[N];20 21 int main(){22     int n, m, k;23     scanf("%d%d%d", &n, &m, &k);24     for(int i = 1; i <= n; ++i){25         scanf("%lld", &s[i]);26         s[i] += s[i-1];27     }28     29     for(int j = 1; j <= k; ++j)30         for(int i = j*m; i <= n; ++i)31            dp[i][j] = max( dp[i - 1][j], dp[i - m][j - 1] + s[i] - s[i-m] );32            33     printf("%lld\n", dp[n][k]);34     35     return 0; 36 }