链接：https://codeforces.com/contest/467/problem/C

这道题是求拿k个子序列且不能相交，问如何拿使得这些序列的值的和最大,那么阶段划分就很明显了，相当于这道问题对应的隐式DAG上一共可以被分成K层，接着就是枚举在哪个点转移，也就是是否取当前的往左m的区间，对应的就是在DAG求最短最长路的时候，是从同一层转移过来还是从前一层转移过来，取最大最小值贪心，类似dijk的思路。

#include<bits/stdc++.h>
using namespace std;
void check_max (int &a,int b) {a=max (a,b);}
typedef long long ll;
const int maxn=5100;
ll a[maxn];
ll dp[maxn][maxn];
ll pre[maxn];

int main () {
  int n,m,k;
  scanf ("%d%d%d",&n,&m,&k);
  ll st=0;
  for (int i=1;i<=n;i++) {
    scanf ("%lld",&a[i]);
    st+=a[i];
    pre[i]=st;
  }
  memset (dp,0,sizeof (dp));
  // for (int j=m;j<=n;j++) 
  //  for (int i=1;i<=k;i++) {
  //   dp[i][j]=max (dp[i][j-1],dp[i-1][j-m]+pre[j]-pre[j-m]);
  //  }
  for (int i=1;i<=k;i++) 
   for (int j=m;j<=n;j++) {
    dp[i][j]=max (dp[i][j-1],dp[i-1][j-m]+pre[j]-pre[j-m]);
   }
  printf ("%lld\n",dp[k][n]);
  return 0;
}