P2331 [SCOI2005]最大子矩阵 （动规：分类讨论状态）

题目链接：传送门

题目：

题目描述

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

输入输出格式

输入格式：

第一行为n,m,k（≤n≤,≤m≤,≤k≤），接下来n行描述矩阵每行中的每个元素的分值(每个元素的分值的绝对值不超过32767)。

输出格式：

只有一行为k个子矩阵分值之和最大为多少。

输入输出样例

输入样例#： 复制

 -

- 

输出样例#： 复制

PS：好像有很多类似的题目，上次的那道中国象棋（放炮的）也是，都是分类讨论多种情况就好了。

思路：

注意到m ≤ 2，所以可以按行dp，分类讨论转移的情况。

　　① 当前行不选；

　　② 当前行选左边；

　　③ 当前行选右边；

　　④ 当前行两个都选，但是作为两个矩阵；

　　⑤ 当前行两个都选，作为同一个矩阵；

以上的m = 2时的情况，m = 1时更简单，只有选或者不选，就不赘述了。

状态：

　　f[i][j][k] 表示当前第i行，构造了j个矩阵，当前行的状态为k，（k = 0 - 4对应上面的① - ⑤）

状态转移方程很容易得出，见代码。

时间复杂度是O(NM⁴K)

#include <bits/stdc++.h>

using namespace std;

const int INF = 0x3f3f3f3f;

const int MAX_N =  + ;

const int MAX_M =  + ;

const int MAX_K =  + ;

inline void tomax(int&a, int b)

{

    a = max(a, b);

}

int mat[MAX_N][MAX_M];

int f[MAX_N][MAX_K][];

int main()

{

    int N, M, K;

    cin >> N >> M >> K;

    for (int i = ; i <= N; i++)

        for (int j = ; j <= M; j++)

            scanf("%d", &mat[i][j]);

    memset(f, -INF, sizeof f);

    for (int i = ; i <= N; i++)

        for (int j = ; j <= K; j++)

            f[i][j][] = ;

    if (M == ) {

        for (int i = ; i <= N; i++)

            for (int j = ; j <= K; j++) {

                tomax(f[i][j][], f[i-][j][]);

                tomax(f[i][j][], f[i-][j][]);

                if (j- >= )

                    tomax(f[i][j][], f[i-][j-][]);

                tomax(f[i][j][], f[i-][j][]);

                f[i][j][] += mat[i][];

            }

        cout << max(f[N][K][], f[N][K][]) << endl;

        return ;

    }

    for (int i = ; i <= N; i++) {

        for (int j = ; j <= K; j++) {

            for (int k = ; k <= ; k++) {

                //0：当前行不选

                tomax(f[i][j][], f[i-][j][k]);

                //1：当前行选左边

                if ((k ==  || k ==  || k == ) && (j- >= ))

                    tomax(f[i][j][], f[i-][j-][k]);

                else if (k ==  || k == )

                    tomax(f[i][j][], f[i-][j][k]);

                //2：当前行选右边

                if ((k <=  || k == ) && j- >= )

                    tomax(f[i][j][], f[i-][j-][k]);

                else if (k ==  || k == )

                    tomax(f[i][j][], f[i-][j][k]);

                //3：当前行左右都选（分开）

                if ((k ==  || k == ) && j- >= )

                    tomax(f[i][j][], f[i-][j-][k]);

                else if ((k ==  || k == ) && j- >= )

                    tomax(f[i][j][], f[i-][j-][k]);

                else if (k == )

                    tomax(f[i][j][], f[i-][j][k]);

                //4：当前行左右都选（一起的）

                if (k !=  && j- >= )

                    tomax(f[i][j][], f[i-][j-][k]);

                else if (k == )

                    tomax(f[i][j][], f[i-][j][k]);

            }

            f[i][j][] += mat[i][];//1：当前行选左边

            f[i][j][] += mat[i][];//2：当前行选右边

            f[i][j][] += mat[i][] + mat[i][];//3：当前行左右都选（分开）

            f[i][j][] += mat[i][] + mat[i][];//4：当前行左右都选（一起的）

        }

    }

    int ans = -INF;

    for (int k = ; k <= ; k++)

        tomax(ans, f[N][K][k]);

    cout << ans;

    return ;

}

/*

3 1 2

1

-1

2

*/

P2331 [SCOI2005]最大子矩阵 （动规：分类讨论状态）的相关教程结束。