欢迎访问~原文出处——博客园-zhouzhendong
去博客园看该题解
题目传送门 - BZOJ1084
题意概括
这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。
输入：第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
题解
注意到1<=m<=2！
如果m = 1 ，那么就是一个简单的线性dp。
我们设dp[i][j]表示在前i个里面选出k个子矩阵的最大分值。
那么分两种情况讨论：
1. 什么都不干： dp[i][j] = max(dp[i][j], dp[i-1][j])
2. 弄一个新的子矩阵： dp[i][j] = max(dp[i][j], dp[x][j - 1] + presum[i] - presum[x]) 0<=x<i
时间复杂度O(kn2)
如果 m = 2 ，那么是一个稍微复杂一点的线性dp。
我们设dp[i][j][x]表示在第一列的前i个和第二列的前j个里面选出x个子矩阵的最大分值。
那么分几种情况进行讨论：
1. 什么都不干： dp[i][j][x] = max(dp[i][j][x], dp[i - 1][j][x], dp[i][j - 1][x])
2. 在第一列弄一个新的子矩阵： dp[i][j][x] = max(dp[i][j][x], dp[y][j][x - 1] + presum[i][1] - presum[y][1]) 0<=y<i
3. 在第二列弄一个新的子矩阵： dp[i][j][x] = max(dp[i][j][x], dp[i][y][x - 1] + presum[j][2] - presum[y][2]) 0<=y<j
4. 在第一、二列弄一个宽度为2的子矩阵： dp[i][j][x] = max(dp[i][j][x], dp[y][y][x - 1] + presum[i][1] - presum[y][1] + presum[j][2] - presum[y][2]) i = j 且 0<=y<i
时间复杂度O(kn3)
代码
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cstdio>
#include <cmath>
using namespace std;
const int N=+,M=,K=+;
const int Inf=<<;
int n,m,k,a[N][M];
void solve1(){
int dp[N][K],presum[N];
for (int i=;i<N;i++)
for (int j=;j<K;j++)
dp[i][j]=-Inf;
presum[]=;
for (int i=;i<=n;i++)
presum[i]=presum[i-]+a[i][];
dp[][]=;
int ans=-Inf;
for (int i=;i<=n;i++)
for (int j=;j<=k;j++){
if (!i&&!j)
continue;
if (i)
dp[i][j]=dp[i-][j];
if (!j)
continue;
for (int x=;x<i;x++)
dp[i][j]=max(dp[i][j],dp[x][j-]+presum[i]-presum[x]);
}
printf("%d",dp[n][k]);
}
void solve2(){
int dp[N][N][K],presum[N][M];
presum[][]=presum[][]=;
for (int i=;i<=n;i++){
presum[i][]=presum[i-][]+a[i][];
presum[i][]=presum[i-][]+a[i][];
}
for (int i=;i<N;i++)
for (int j=;j<N;j++)
for (int x=;x<K;x++)
dp[i][j][x]=-Inf;
dp[][][]=;
for (int i=;i<=n;i++)
for (int j=;j<=n;j++)
for (int x=;x<=k;x++){
if (!i&&!j&&!x)
continue;
if (i&&j)
dp[i][j][x]=max(dp[i-][j][x],dp[i][j-][x]);
else if (i)
dp[i][j][x]=dp[i-][j][x];
else if (j)
dp[i][j][x]=dp[i][j-][x];
if (!x)
continue;
for (int y=;y<i;y++)
dp[i][j][x]=max(dp[i][j][x],dp[y][j][x-]+presum[i][]-presum[y][]);
for (int y=;y<j;y++)
dp[i][j][x]=max(dp[i][j][x],dp[i][y][x-]+presum[j][]-presum[y][]);
if (i==j)
for (int y=;y<i;y++)
dp[i][j][x]=max(dp[i][j][x],dp[y][y][x-]+presum[i][]-presum[y][]+presum[j][]-presum[y][]);
}
printf("%d",dp[n][n][k]);
}
int main(){
scanf("%d%d%d",&n,&m,&k);
for (int i=;i<=n;i++)
for (int j=;j<=m;j++)
scanf("%d",&a[i][j]);
if (m==)
solve1();
else
solve2();
return ;
}