DP
此题可以分为两个子问题。
(m)等于(1):
原题目转化为求一行数列里的(k)块区间的和，区间可以为空的值。
直接定义状态(dp[i][t])表示前i个数分为t块的最大值。
因为区间可以为空，所以最大值再小也不会比0小，所以初始化(dp)值为(0)。
有方程(dp[i][t]=max(dp[i-1][t],dp[j][t-1]+sum_{k=j+1}^{i}a[k]))
考虑顺序及边界，发现此时的(dp[i][t])是从(t-1)块转移过来的，所以(j)要和(i)断开。但是又因为可以从(1)一路取到(i)，因此(j+1)可以取到(1)。所以(0<=j<i)，而且(t)要放在循环的最外面。
(m)等于(2):
同样可以(dp)，定义状态(dp[i][j][t])为第一列取到(i)，第二列取到(j)，分为(t)块的最大值。
有方程(dp[i][j][t]=max(dp[i-1][j][t],dp[i][j-1][t],dp[o][j][t-1]+sum_{k=o+1}^{i}a[k][1],dp[i][o][t-1]+sum_{k=o+1}^{j}a[k][2]);)
如果i等于j的话，还有方程
(dp[i][j][t]=max(dp[i][j][t],dp[o][o][t-1]+sum_{k=o+1}^ia[k][1]+a[k][2]);)
顺序及边界和第一问一样。
#include <bits/stdc++.h>
#define N 1001
using namespace std;
int n, m, k, maxn;
int dp[N][N][40], a[N][N], sum1[N], sum2[N], dp1[N][40];
int Max(int a, int b, int c, int d) {return max(max(a, b), max(c, d));}
int Q1(int i, int j)
{
return sum1[j] - sum1[i - 1];
}
int Q2(int i, int j)
{
return sum2[j] - sum2[i - 1];
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
if (m == 1)
{
for (int i = 1; i <= n; i++)
scanf("%d", &a[i][1]), sum1[i] = sum1[i - 1] + a[i][1];
for (int t = 1; t <= k; t++)
for (int i = 1; i <= n; i++)
{
dp1[i][t] = dp1[i - 1][t];
for (int j = 0; j < i; j++)
dp1[i][t] = max(dp1[i][t], dp1[j][t - 1] + Q1(j + 1, i));
}
printf("%d", dp1[n][k]);
}
else
{
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &a[i][j]);
for (int i = 1; i <= n; i++)
sum1[i] = sum1[i - 1] + a[i][1],
sum2[i] = sum2[i - 1] + a[i][2];
for (int i = 1; i <= n; i++)
dp[i][0][1] = sum1[i], dp[0][i][1] = sum2[i];
for (int t = 1; t <= k; t++)
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
{
dp[i][j][t] = max(dp[i - 1][j][t], dp[i][j - 1][t]);
for (int o = 0; o < i; o++)//选择到第i位。
dp[i][j][t] = max(dp[i][j][t], dp[o][j][t - 1] + Q1(o + 1, i));
for (int o = 0; o < j; o++)
dp[i][j][t] = max(dp[i][j][t], dp[i][o][t - 1] + Q2(o + 1, j));
if (i == j)
for (int o = 0; o < i; o++)
dp[i][j][t] = max(dp[i][j][t], dp[o][o][t - 1] + Q1(o + 1, i) + Q2(o + 1, j));
}
printf("%d", dp[n][n][k]);
}
return 0;
}