原题链接
题目描述：这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入格式：第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式：只有一行为k个子矩阵分值之和最大为多少。
输入样例： 3 2 2 1 -3 2 3 -2 3
输出格式： 9
解析：注意1≤m≤2！ 当m=1时，很容易想到可以用DP解决。 设dp[i][j]表示前i个数，取了j个矩阵的最大值。 如果不选，dp[i][j]=max(dp[i][j],dp[i-1][j)。 如果选，dp[i][j]=max(dp[i][j],dp[l][j-1]+sum[i]-sum[l])。 当m=2时，也考虑用DP进行解决。 设f[i][j][k]表示第一列选到了第i个，第二列选到了第j个，一共选了k个矩阵的最大值。 那么有以下几种情况。 若不选，f[i][j][k]=max(f[i-1][j][k],f[i][j-1][k])。 若只选第一列，f[i][j][k]=max(f[i][j][k],f[l][j][k-1]+sum[i][0]-sum[l][0])。 若只选第二列，f[i][j][k]=max(f[i][j][k],f[i][l][k-1]+sum[j][1]-sum[l][1])。 当i=j时，可以两行都选。 同时可以两行当成一个矩阵选，也可以当成两个矩阵选。 若当成一个矩阵，f[i][j][k]=max(f[i][j][k],f[l][l][k-1]+sum[i][0]-sum[l][0]+sum[j][1]-sum[l][1])。 若当成两个矩阵，f[i][j][k]=max(f[i][j][k],f[l][l][k-2]+sum[i][0]-sum[l][0]+sum[j][1]-sum[l][1])。
代码如下：
#include<cstdio> #include<algorithm> using namespace std; const int maxn = 105; int n, m, k, a[maxn][maxn], dp[maxn][maxn], sum[maxn][2]; int f[maxn][maxn][maxn]; int read(void) { char c; while (c = getchar(), (c < '0' || c > '9') && c != '-'); int x = 0, y = 1; if (c == '-') y = -1; else x = c - '0'; while (c = getchar(), c >= '0' && c <= '9') x = x * 10 + c - '0'; return x * y; } void subtask1(void) { for (int i = 1; i <= n; ++ i) sum[i][0] = sum[i - 1][0] + a[i][1]; for (int i = 1; i <= n; ++ i) for (int j = 1; j <= k; ++ j) for (int h = i - 1; h >= 0 ; -- h) { dp[i][j] = max(dp[i][j], dp[i - 1][j]); dp[i][j] = max(dp[i][j], dp[h][j - 1] + sum[i][0] - sum[h][0]); } printf("%d", dp[n][k]); } void subtask2(void) { for (int i = 1; i <= n; ++ i) { sum[i][0] = sum[i - 1][0] + a[i][1]; sum[i][1] = sum[i - 1][1] + a[i][2]; } for (int i = 1; i <= n; ++ i) for (int j = 1; j <= n; ++ j) for (int h = 1; h <= k; ++ h) { f[i][j][h] = max(f[i - 1][j][h], f[i][j - 1][h]); for (int l = i - 1; l >= 0; -- l) f[i][j][h] = max(f[i][j][h], f[l][j][h - 1] + sum[i][0] - sum[l][0]); for (int l = j - 1; l >= 0; -- l) f[i][j][h] = max(f[i][j][h], f[i][l][h - 1] + sum[j][1] - sum[l][1]); if (i == j) { for (int l = i - 1; l >= 0; -- l) { f[i][j][h] = max(f[i][j][h], f[l][l][h - 1] + sum[i][0] - sum[l][0] + sum[j][1] - sum[l][1]); if (h > 1) f[i][j][h] = max(f[i][j][h], f[l][l][h - 2] + sum[i][0] - sum[l][0] + sum[j][1] - sum[l][1]); } } } printf("%d", f[n][n][k]); } int main() { n = read(); m = read(); k = read(); for (int i = 1; i <= n; ++ i) for (int j = 1; j <= m; ++ j) a[i][j] = read(); if (m == 1) subtask1(); else subtask2(); return 0; }转载于:https://www.cnblogs.com/Gaxc/p/10205442.html
