http://acm.hdu.edu.cn/showproblem.php?pid=1024
刚开始的时候没看懂题目，以为一定要把那n个数字分成m对，然后求m对中和值最大的那对
但是不是，题目说的只是选出m对，所以有些数字是可以不用的。
那么就用
dp[i][j]表示前j个数，分成了i段，其中第a[j]个数必定包含在第i段之中的最大和值。就是a[j]必定选了而且在第i段之中。
至于为什么要这样设。
1、如果想得到ans，只需要扫描一次ans = max(ans, dp[m][m....n])，因为第m段肯定是以a[]中某个数字结尾。同时至少要有m个数才能分成m段
2、更多的是看做题量，很多dp都是这样设，（最大字段和等）。所以dp靠得还是经验，我还是去多多刷题补上我的弱项----dp
转移：
对于每个a[j]，要么，a[j]独立一组（独立在第i组上），所以此时的贡献是max(dp[i - 1][k]) + a[j]，其中 i - 1 <= k <= j - 1
k为什么要大于等于i - 1呢，因为起码要有i - 1个数才能组成i - 1组。然后选取最大的来和a[j]组合成i个组。
要么, a[j]在第i组上但是a[j - 1]也在第i组上（这样是用来判断和前面的连接成一个组的） 贡献:dp[i][j - 1] + a[j]
直接转移m * n * n
考虑到第一个转移的时候，肯定是从dp[i - 1][k]中选一个最大的来和a[j]相加，所以考虑到用个preMx[j]表示前j个数在分成i - 1个组时候的最大值。能压缩成n * m
因为dp只和上一维有关，故可以用滚动数组压缩空间、
滚动数组就是，
例如现在要算分成i个组的，那么你分成i - 2个组的已经没用了，故可以舍弃
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
#define IOS ios::sync_with_stdio(false)
using namespace std;
#define inf (0x3f3f3f3f)
typedef long long int LL; #include <iostream>
#include <sstream>
#include <vector>
#include <set>
#include <map>
#include <queue>
#include <string>
const int maxn = + ;
LL dp[maxn];
LL preMx[][maxn];
int a[maxn];
int n, m;
void work() {
for (int i = ; i <= n; ++i) {
preMx[][i] = ;
preMx[][i] = ;
dp[i] = ;
}
for (int i = ; i <= n; ++i) scanf("%d", &a[i]);
int now = ;
LL mx;
for (int i = ; i <= m; ++i) {
mx = -inf;
for (int j = i; j <= n; ++j) { //因为分成i组，起码要有i个数
dp[j] = max(preMx[!now][j - ] + a[j], dp[j - ] + a[j]);
mx = max(mx, dp[j]);
preMx[now][j] = mx;
}
now = !now;
}
printf("%I64d\n", mx);
}
int main() {
#ifdef local
freopen("data.txt","r",stdin);
#endif
while (scanf("%d%d", &m, &n) != EOF) work();
return ;
}