题目大意：从n个数中选出m段不相交的子串，子串的长度均为k，问所有选出来的子串的所有数的和最大为多少。
DP题，DP还是太弱，开始时的dp方程居然写成了O(n^3)...
dp[i][j]: 以num[i]结尾的序列，分成j段的最大和
dp[i][j]=max(dp[k][j-1]+sum[i]-sum[i-m]) 这样的话，其实只要第一重循环是选的段数，第二重循环时数字个数
我又换了种思路
dp[i][j]: 前i个数，分成j段的最大和
dp[i][j]=max(dp[i-1][j],dp[i-m][j-1]+sum[i]-sum[i-m])
思路：二维嘛，所以写出来的dp方程肯定是要么从第一维变化转移过来的，要么从第二维的变化转移过来的
AC代码：
//#pragma comment(linker, "/STACK:102400000,102400000")#include <cstdio>#include <cstring>#include <algorithm>#include <string>#include <iostream>#include <iomanip>#include <cmath>#include <map>#include <set>#include <queue>using namespace std;#define ls(rt) rt*2#define rs(rt) rt*2+1#define ll long long#define ull unsigned long long#define rep(i,s,e) for(int i=s;i<e repe for i="s;i<=e;i++)#define" cl memset in freopen out ll ll_inf="((ull)(-1))">>1;const double EPS = 1e-8;const double pi = acos(-1);const int INF = 100000000;const int MAXN = 5000+100;ll num[MAXN],dp[MAXN][MAXN],pp[MAXN];int n,m,k;ll solve(){ CL(dp,0); for(int i=m;i <br> 第一种思路的AC代码（摘自 http://blog.csdn.net/qian99/article/details/39397101）： <br> <br> <p></p> <p></p> <pre name="code" class="sycode">#include<iostream> #include<cstdio> #include<cstring> #include<string> #include<algorithm> #include<map> #include<queue> #include<stack> #include<set> #include<cmath> #include<vector> #define inf 0x3f3f3f3f #define Inf 0x3FFFFFFFFFFFFFFFLL #define eps 1e-8 #define pi acos(-1.0) using namespace std; typedef long long ll; const int maxn = 5000 + 5; int a[maxn]; ll sum[maxn],dp[maxn][maxn],maxv[maxn]; int main() { // freopen("in.txt","r",stdin); // freopen("out.txt","w",stdout); int n,m,k; scanf("%d%d%d",&n,&m,&k); for(int i = 1;i = 0) { dp[i][j] = max(dp[i][j],maxv[i-m] + sum[i] - sum[i-m]); } } for(int i = 1;i <br> <br> <p></p> </vector></cmath></set></stack></queue></map></algorithm></string></cstring></cstdio></iostream>
