Jeekr's site
0%

[SCOI2005] 最大子矩阵

Posted on Edited on

这是一道状压dp的题目。似乎这道题简洁明了的做法还没有，那么我就来简单地给出一份还可以的代码。详见代码。 很显然，我们按照长条状考虑，每列算一个阶段，每个阶段只与前一个有关。每个阶段有5*(k+1)个状态，对应形状和已选矩阵数量。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
#include <bits/stdc++.h>;
using namespace std;
const int N = 110, M = 3, K = 11;
int dp[N][K][5];
int a[N][M];
int main()
{
    int n, m, k;
    cin >;>; n >;>; m >;>; k;
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            cin >;>; a[i][j];

    memset(dp, 0xa0, sizeof dp);
    dp[0][0][0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        for (int kk = 0; kk <= k; ++kk)
        {
            // 0 不选
            for (int s = 0; s <= 4; ++s)
                dp[i][kk][0] = max(dp[i][kk][0], dp[i - 1][kk][s]);
            // 可以从任意状态转移来

            // 1 上 2 下
            for (int w = 1; w <= 2; ++w)
            {
                if (kk)
                    for (int s = 0; s <= 4; ++s)
                        dp[i][kk][w] = max(dp[i][kk][w], dp[i - 1][kk - 1][s] + a[i][w]);
                // 从上方某个状态转移来，花费1次数

                dp[i][kk][w] = max(dp[i][kk][w], dp[i - 1][kk][w] + a[i][w]);
                dp[i][kk][w] = max(dp[i][kk][w], dp[i - 1][kk][4] + a[i][w]);
                // 这是不花费多余次数的
            }
            // 3 上下整体
            if (kk)
                for (int s = 0; s <= 4; ++s)
                    dp[i][kk][3] = max(dp[i][kk][3], dp[i - 1][kk - 1][s] + a[i][1] + a[i][2]);

            dp[i][kk][3] = max(dp[i][kk][3], dp[i - 1][kk][3] + a[i][1] + a[i][2]);

            // 4 上下分开
            dp[i][kk][4] = max(dp[i][kk][4], dp[i - 1][kk][4] + a[i][1] + a[i][2]);
            if (kk)
            {
                if (kk >;= 2)
                    for (int s = 0; s <= 4; ++s)
                        dp[i][kk][4] = max(dp[i][kk][4], dp[i - 1][kk - 2][s] + a[i][1] + a[i][2]);
                        //  继承2个
                dp[i][kk][4] = max(dp[i][kk][4], dp[i - 1][kk - 1][1] + a[i][1] + a[i][2]);
                dp[i][kk][4] = max(dp[i][kk][4], dp[i - 1][kk - 1][2] + a[i][1] + a[i][2]);
                // 继承1个
            }
        }
    }

    int ans = 0xa0a0a0a0;
    for (int kk = 0; kk <= 4; ++kk)
        ans = max(ans, dp[n][k][kk]);
    cout << ans << endl;
}