Description
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵
不能相互重叠。
Input
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的
分值的绝对值不超过32767)。
Output
只有一行为k个子矩阵分值之和最大为多少。
Sample Input
3 2 2
1 -3
2 3
-2 3
Sample Output
9
HINT
Source
思路： m只有2！！！
m=1的时候设dp[i][t]为到了第i个点分为选t个子块的最大价值。状态选择过程是加上末尾这一段或者不加上末尾这一段。加上末尾这一段就从dp[j][t-1]，j ≤ i 转移过来。不选择末尾这一段，就从前面某个地方为终点是分为t段的最优状态转移过来，也就是dp[j][t]。
m=2的时候也是类似思路，子矩阵高只有1或者2，分类讨论就可以了。讨论第一行的末尾这一段选不选，或者第二行的末尾选不选。如果第一二行结尾相同，那么就可以有高度为2的子矩阵，就讨论末尾处高度为2的子矩阵选不选。
ACNEW
#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;int f1[105][15],f2[105][105][15];
int s1[105],s2[105];int main()
{int n,m,K;scanf("%d%d%d",&n,&m,&K);if(m == 1){for(int i = 1;i <= n;i++){int s;scanf("%d",&s);s1[i] = s1[i - 1] + s;}for(int i = 1;i <= n;i++){for(int k = 1;k <= K;k++){f1[i][k] = f1[i - 1][k];for(int j = 0;j < i;j++){f1[i][k] = max(f1[i][k],f1[j][k - 1] + s1[i] - s1[j]);}}}printf("%d\n",f1[n][K]);}else if(m == 2){for(int i = 1;i <= n;i++){int a,b;scanf("%d%d",&a,&b);s1[i] = s1[i - 1] + a;s2[i] = s2[i - 1] + b;}for(int k = 1;k <= K;k++){for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j++){f2[i][j][k] = max(f2[i - 1][j][k],f2[i][j - 1][k]);for(int l = 0;l < i;l++){f2[i][j][k] = max(f2[i][j][k],f2[l][j][k - 1] + s1[i] - s1[l]);}for(int l = 0;l < j;l++){f2[i][j][k] = max(f2[i][j][k],f2[i][l][k - 1] + s2[j] - s2[l]);}if(i == j){for(int l = 0;l < i;l++){f2[i][j][k] = max(f2[i][j][k],f2[l][l][k - 1] + s1[i] - s1[l] + s2[i] - s2[l]);}}}}}printf("%d\n",f2[n][n][K]);}return 0;
}#include <cstdio>
#include <cstring>
#include <algorithm>using namespace std;
const int maxn = 100 + 7;int n,m,k;
int sum1[maxn],sum2[maxn],dp1[maxn][20],dp2[maxn][maxn][20];void solve1()
{for(int i = 1;i <= n;i++){int x;scanf("%d",&x);sum1[i] = sum1[i - 1] + x;}for(int i = 1;i <= n;i++){for(int j = 0;j < i;j++){for(int t = 1;t <= k;t++){dp1[i][t] = max(dp1[i][t],dp1[j][t - 1] + sum1[i] - sum1[j]);dp1[i][t] = max(dp1[i][t],dp1[j][t]);}}}printf("%d\n",dp1[n][k]);
}void solve2()
{for(int i = 1;i <= n;i++){int x,y;scanf("%d%d",&x,&y);sum1[i] = sum1[i - 1] + x;sum2[i] = sum2[i - 1] + y;}for(int i = 1;i <= n;i++){for(int j = 1;j <= n;j ++){if(i == j){for(int x = 0;x < i;x++){for(int t = 1;t <= k;t++){dp2[i][j][t] = max(dp2[i][j][t],dp2[x][x][t - 1] + sum1[i] - sum1[x] + sum2[j] - sum2[x]);dp2[i][j][t] = max(dp2[i][j][t],dp2[x][x][t]);}}}for(int x = 0;x < i;x++){for(int t = 1;t <= k;t++){dp2[i][j][t] = max(dp2[i][j][t],dp2[x][j][t - 1] + sum1[i] - sum1[x]);dp2[i][j][t] = max(dp2[x][j][t],dp2[i][j][t]);}}for(int x = 0;x < j;x++){for(int t = 1;t <= k;t++){dp2[i][j][t] = max(dp2[i][j][t],dp2[i][x][t - 1] + sum2[j] - sum2[x]);dp2[i][j][t] = max(dp2[i][x][t],dp2[i][j][t]);}}}}printf("%d\n",dp2[n][n][k]);
}int main()
{scanf("%d%d%d",&n,&m,&k);if(m == 1)solve1();if(m == 2)solve2();return 0;
}