给你一个序列n个数组成，然后让你在里面找到m个子序列，让这m个子序列的和最大。
思路：
dp[i][j]表示的是第j个数字在第i个子序列时的当前最优值。
dp[i][j] = maxx(dp[i][j-1] + num[j] ,maxx(dp[i-1][k]) + num[j]); k是从1到j-1.
可以这么理解这个转移方程，对于当前的这个数字，如果把他放到第i个子序列中有两种情况，一个是他作为第i个子序列的第一个数字，另一个就是不作为第一个数字，作为第一个数字的时候是 maxx(dp[i-2][k] + num[j]) 1<=k<i 的意思是从之前的所有中找到i-1个子序列的最大值+当前的值，不做为第一个的时候那么他前面的那个数字一定是i序列的，同一个子序列，又不是作为第一个，那么前面的那个货就一定是同一个子序列的，那么当前的值是dp[i][j-1] + num[j],在两种决策中选择一个最有的就行了，还有就是maxx(dp[i-1][k]+num[j])的这个地方可以开一个数组记录下来，不能每次都跑，跑不起，再有就是这个题目没有给m的范围，所以开不了二维数组（目测不是很大，大的话会超时，但是肯定是先超内存在超时，所以为了保险，还是吧dp[][]压缩成一维的）那么状态转移就边成这样了dp[j]表示的是 j这个人在当前的这个子序列中的最优值，mk[j]表示的是在上一个子序列中1--j的dp的最大值，所以就变成 dp[j] = maxx(dp[j-1] + num[j] ,mk[j-1]+num[j]);还是 max(作为i个子序列的第一个元素，不是第一个元素取一个最大值)。在解释下代码的核心部分。
__int64 Max
for(i = 1 ;i <= m ;i ++) //枚举子序列
{
Max = - INF;
for(j = i ;j <= n ;j ++) //j = i是因为每个子序列最少1个元素
{
if(i == j) dp[j] = mk[j-1] + num[j];//第i个元素只能是第i个子序列的第一个
else
dp[j] = maxx(dp[j-1] ,mk[j-1]) + num[j];
mk[j-1] = Max; //这个地方注意了，不能更新mk[j]，只能更新j-1因为更新j就会被当前的这个子序列更新的时候用到。
if(Max < dp[j]) Max = dp[j];
}
}
最后直接输出Max就行了，因为里面保存的正好是第m个子序列中最大的那个。
#include<stdio.h> #include<string.h> #define N 110000 #define INF 922337203685477580 __int64 num[N] ,dp[N] ,mk[N]; __int64 maxx(__int64 x ,__int64 y) { return x > y ? x : y; } int main () { int n ,m ,i ,j; while(~scanf("%d %d" ,&m ,&n)) { for(i = 1 ;i <= n ;i ++) scanf("%I64d" ,&num[i]); memset(dp ,0 ,sizeof(dp)); memset(mk ,0 ,sizeof(mk)); __int64 Max; for(i = 1 ;i <= m ;i ++) { Max = -INF; for(j = i ;j <= n ;j ++) { if(i == j) dp[j] = mk[j-1] + num[j]; else dp[j] = maxx(dp[j-1] ,mk[j-1]) + num[j]; mk[j-1] = Max; if(Max < dp[j]) Max = dp[j]; } } printf("%I64d " ,Max); } return 0; }