题目链接：
https://www.lydsy.com/JudgeOnline/problem.php?id=1084
题目大意：
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。n<=100 m<=2
思路：
m=1时，就是数组选出k个连续子段和最大。
dp[i][j]表示前i个数中已经取了j个连续子段和的最优解。
dp[i][j] = dp[i-1][j] 不取这个数
dp[i][j] = dp[start-1][j-1] + s[start]+…+s[i] 取这个数，并且从start到i作为第j个连续段（求区间和直接用前缀和求差代替）
m=2时
dp[i][j][k]表示第一列前i个数 第2列前j个数，已经取了k个子矩阵的最优解
dp[i][j][k] = max(dp[i-1][j][k], dp[i][j-1][k]) 不取这个数
dp[i][j][k] = dp[start-1][j][k-1] + s[start][1]+…+s[i][1] 第一列从start到i取出来作为第k个子矩阵
dp[i][j][k] = dp[i][start-1][k-1] + s[start][2]+…+s[i][2] 第二列从start到i取出来作为第k个子矩阵
dp[i][j][k] = dp[start-1][start-1][k-1] + s[start][1]+…+s[i][1]+s[start][2]+…+s[j][2]当且仅当i==j 两列同时取。
同样的，区间求和用前缀和快速求出。
时间复杂度为O(n^3*k)
#include<bits/stdc++.h>
#define IOS ios::sync_with_stdio(false);//不可再使用scanf printf
#define Max(a, b) ((a) > (b) ? (a) : (b))//禁用于函数，会超时
#define Min(a, b) ((a) < (b) ? (a) : (b))
#define Mem(a) memset(a, 0, sizeof(a))
#define Dis(x, y, x1, y1) ((x - x1) * (x - x1) + (y - y1) * (y - y1))
#define MID(l, r) ((l) + ((r) - (l)) / 2)
#define lson ((o)<<1)
#define rson ((o)<<1|1)
#define Accepted 0
#pragma comment(linker, "/STACK:102400000,102400000")//栈外挂
using namespace std;
inline int read()
{
int x=,f=;char ch=getchar();
while (ch<''||ch>''){if (ch=='-') f=-;ch=getchar();}
while (ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}
return x*f;
} typedef long long ll;
const int maxn = + ;
const int MOD = ;//const引用更快，宏定义也更快
const int INF = 1e9 + ;
const double eps = 1e-;
int dp1[maxn][];//m = 1 dp1[i][j]表示前i个数中取了j个连续段的最大值
int dp2[maxn][maxn][];//m = 2 dp2[i][j][k]表示第一列前i个数第二列前j个数取了k个连续段的最大值
int s[maxn];
int sum[maxn][];
int main()
{
int n, m, K;
scanf("%d%d%d", &n, &m, &K);
if(m == )
{
for(int i = ; i <= n; i++)scanf("%d", &s[i]), s[i] += s[i - ];//直接记录前缀和
for(int i = ; i <= n; i++)
for(int j = ; j <= K; j++)dp1[i][j] = -INF;//dp[i][0]均为初始化的0
for(int i = ; i <= n; i++)
{
for(int j = ; j <= K; j++)
{
dp1[i][j] = dp1[i - ][j];//不取这个数字
for(int start = ; start <= i; start++)//从start开始一直取到i作为第j段
{
dp1[i][j] = max(dp1[i][j], dp1[start - ][j - ] + s[i] - s[start - ]);
}
}
}
printf("%d\n", dp1[n][K]);
}
else
{
for(int i = ; i <= n; i++)
{
for(int j = ; j <= m; j++)
{
scanf("%d", &sum[i][j]);
sum[i][j] += sum[i - ][j];//记录每一列的前缀和
}
}
for(int i = ; i <= n; i++)for(int j = ; j <= n; j++)for(int k = ; k <= K; k++)dp2[i][j][k] = -INF;
for(int i = ; i <= n; i++)
for(int j = ; j <= n; j++)for(int k = ; k <= K; k++)
{
dp2[i][j][k] = max(dp2[i - ][j][k], dp2[i][j - ][k]);//不取这个数字
for(int start = ; start <= i; start++)//第一列从start开始一直取到i作为第k个矩阵
dp2[i][j][k] = max(dp2[i][j][k], dp2[start - ][j][k - ] + sum[i][] - sum[start - ][]);
for(int start = ; start <= j; start++)//第二列从start开始一直取到j作为第k个矩阵
dp2[i][j][k] = max(dp2[i][j][k], dp2[i][start - ][k - ] + sum[j][] - sum[start - ][]);
if(i == j)//两列从start开始一直取到i作为第k个矩阵
{
for(int start = ; start <= i; start++)
dp2[i][j][k] = max(dp2[i][j][k], dp2[start - ][start - ][k - ] + sum[i][] + sum[i][] - sum[start - ][] - sum[start - ][]);
}
}
printf("%d\n", dp2[n][n][K]);
}
return Accepted;
}
