题解 [SCOI2005]最大子矩阵

题目描述

这里有一个n*m的矩阵，请你选出其中k个子矩阵，使得这个k个子矩阵分值之和最大。注意：选出的k个子矩阵不能相互重叠。

输入输出格式

输入格式
第一行为n,m,k（1≤n≤100,1≤m≤2,1≤k≤10），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。
输出格式
只有一行为k个子矩阵分值之和最大为多少。

输入输出样例

输入样例#1

3 2 2
1 -3
2 3
-2 3

输出样例#1

9

解题思路

发现数据范围对于 m 的限制很特殊， m 只有可能为 1 或 2 两种情况，那么我们先预处理出两个前缀和，分别表示矩阵中两列的分数，然后再对于这两种情况分开考虑即可
首先对于 m = 1 这样的数据，矩阵只有一列，呢么我们定义状态变量为 f [ i ] [ k ] 表示当前考虑了前 i 行，选了 k 个子矩阵的最大分数，当我们每枚举到一个 k 时，现将 f [ i ] [ k ] 赋值为 f [ i - 1 ] [ k ]，表示选了 k 个矩阵， i 不在矩阵 k 中的情况，然后开始枚举一个 h ，表示 i 所在的这个矩阵的起点位置，找出这个起点 h 在哪时所得的分数最大，转移方程即为：

f [ i ] [ k ]=max( f [ i ] [ k ] , f [ h - 1 ] [ k - 1 ] + ( sum [ i ] - sum [ h - 1 ] ) );

当 m = 2 时，我们就需要对状态变量增加一个维度，即为 f [ i ] [ j ] [ k ] 表示第一列考虑了前 i 个数，第二列考虑了前 j 个数，选取了 k 个矩阵时的最大分值，对于每一列的状态转移与 m = 1 时的情况类似，在此不做赘述，而在这种情况中有一种特殊的情况是需要我们重新考虑的，即为 i , j 都被选入第 k 个矩阵时的情况，这种情况只有可能在 i = j 时发生，故在这种情况下的状态转移方程即为：

f [ i ] [ j ] [ k ] = max ( f [ i ] [ j ] [ k ] , f [ h - 1 ] [ h - 1 ] [ k - 1 ] + ( sum1 [ i ] - sum1 [ h - 1 ] ) + ( sum2 [ j ] - sum2 [ h - 1 ] ) ) ;

具体细节看代码注释，下面是C++代码

C++代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int maxn=110;
int n,m,K;
int a[maxn][3];
int f[maxn][15],dp[maxn][maxn][15],sum1[maxn],sum2[maxn];

inline int read(){//珂朵莉版快读~~~
    int chtholly=0,willem=1;char c=getchar();
    while(c<'0' || c>'9'){if(c=='-')willem=-1;c=getchar();}
    while(c<='9' && c>='0'){chtholly=chtholly*10+(int)(c-'0');c=getchar();}
    return chtholly*willem;
}

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(j==1)sum1[i]=sum1[i-1]+a[i][j];
        else sum2[i]=sum2[i-1]+a[i][j];//预处理前缀和
    }
    if(m==1){//考虑m=1的情况
        for(int i=1;i<=n;i++)for(int k=1;k<=K;k++){
            f[i][k]=f[i-1][k];for(int h=1;h<=i;h++)
                f[i][k]=max(f[i][k],f[h-1][k-1]+(sum1[i]-sum1[h-1]));
        }
        printf("%d\n",f[n][K]);
        return 0;
    }
    //考虑m=2的情况
    for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)for(int k=1;k<=K;k++){
        dp[i][j][k]=max(dp[i-1][j][k],dp[i][j-1][k]);
        for(int h=1;h<=i;h++)//对第一列进行转移
            dp[i][j][k]=max(dp[i][j][k],dp[h-1][j][k-1]+(sum1[i]-sum1[h-1]));
        for(int h=1;h<=j;h++)//对第二列进行转移
            dp[i][j][k]=max(dp[i][j][k],dp[i][h-1][k-1]+(sum2[j]-sum2[h-1]));
        if(i==j)//考虑i和j都选入k的情况
            for(int h=1;h<=i;h++)
                dp[i][j][k]=max(dp[i][j][k],dp[h-1][h-1][k-1]+(sum1[i]-sum1[h-1])+(sum2[j]-sum2[h-1]));
    }
    printf("%d\n",dp[n][n][K]);
    return 0;
}