[SCOI2005]最大子矩阵

题目链接

题意

给你n * m 的矩阵 n <= 100 m <= 2;
让你从这个矩阵中选k个不相交的子矩阵，问最大的和是多少。

题解

这题，，一看到我就不知道该怎么下手，想半天想不出来个啥，啥都想不出来，遇到这种多维的dp就不知道怎么下手，很烦。
题解：
因为最多有两列
dp数组：dp[i][j][k] 表示 第一列前i个跟第二列前j个可以出k组的最大值是多少。
状态转移：

dp[i][j][p] = max(dp[i][j - 1][p],dp[i - 1][j][p]);
for (int t = 0; t < i; t ++ )
{
   
	dp[i][j][p] = max(dp[i][j][p],dp[t][j][p - 1] + s[i][1] - s[t][1]);
}
for (int t= 0; t < j; t ++ )
{
   
	dp[i][j][p] = max(dp[i][j][p],dp[i][t][p - 1] + s[j][2] - s[t][2]);
}

但是这样并不是子矩阵，因为子矩阵可能是两列合并成一个的情况。
两列合并成一列只有在i == j的情况下合并。

if(i == j)
{
   
	for (int t=  0; t < i; t ++ )
	{
   
		dp[i][j][p] = max(dp[i][j][p],dp[t][t][p -1 ] + s[i][1] - s[t][1] + s[j][2] - s[t][2]);
	}
}

代码:

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <cmath>
#include <set>
#include <cstring>
#include <string>
#include <bitset>
#include <stdlib.h>
#include <time.h> 
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef unsigned long long ull;
#define st first
#define sd second
#define mkp make_pair
#define pb push_back
void wenjian(){
   freopen("concatenation.in","r",stdin);freopen("concatenation.out","w",stdout);}
void tempwj(){
   freopen("hash.in","r",stdin);freopen("hash.out","w",stdout);}
ll gcd(ll a,ll b){
   return b == 0 ? a : gcd(b,a % b);}
ll qpow(ll a,ll b,ll mod){
   a %= mod;ll ans = 1;while(b){
   if(b & 1)ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;}
struct cmp{
   bool operator()(const pii & a, const pii & b){
   return a.second > b.second;}};
int lb(int x){
   return  x & -x;}

const int inf = 0x3f3f3f3f;
const ll INF = 0x3f3f3f3f3f3f3f3f;
const ll mod = 1e9+7;
const int maxn = 105;
int a[maxn][3];
int s[maxn][3];
int dp[maxn][maxn][15];//第一列取i个第二列取j个 总共k组 的最大值
int main()
{
   
	int n,m,k;
	scanf("%d%d%d",&n,&m,&k);
	for (int i = 1; i <= n; i++ )
	{
   
		for (int j = 1; j <= m; j ++ )
		{
   
			scanf("%d",&a[i][j]);
			s[i][j] = s[i - 1][j] + a[i][j];
		}
	}
	for (int i = 1; i <= n; i ++ )
	{
   
		for (int j = 1; j <= n; j ++ )
		{
   
			for (int p = 1; p <= k; p ++ )
			{
   
				dp[i][j][p] = max(dp[i][j - 1][p],dp[i - 1][j][p]);
				for (int t = 0; t < i; t ++ )
				{
   
					dp[i][j][p] = max(dp[i][j][p],dp[t][j][p - 1] + s[i][1] - s[t][1]);
				}
				for (int t= 0; t < j; t ++ )
				{
   
					dp[i][j][p] = max(dp[i][j][p],dp[i][t][p - 1] + s[j][2] - s[t][2]);
				}
				if(i == j)
				{
   
					for (int t=  0; t < i; t ++ )
					{
   
						dp[i][j][p] = max(dp[i][j][p],dp[t][t][p -1 ] + s[i][1] - s[t][1] + s[j][2] - s[t][2]);
					}
				}
			}
		}
	}
	printf("%d\n",dp[n][n][k]);
}