Rockdu's Blog

题目描述

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

输入输出格式

输入格式：

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

输出格式：

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

输入输出样例

3 2 2
1 -3
2 3
-2 3

9​​

xo ox xx oo
xo xo xo xo
1  2  3  4

可是问题就来了，1、2、4状态都很好转移，但是3的转移举步维艰。为了能顺利的转移，我们再引入一个新的状态(Xx 100) 表示现在选取的两个数左右分别一个矩形，并且用原来的xx表示现在选的两个数在同一个矩形。代码就写好了（极长的状态转移）：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define ox 1
#define xo 2
#define oo 0
#define xx 3
using namespace std;
const int inf = 0x3f3f3f3f;
int dp[105][12][4], n, m, k, mp[105][2], tmp[2][4], mx;
int main() {
    scanf("%d%d%d", &n, &m, &k);
    for(register int i = 1; i <= n; ++i)
        for(register int j = 0; j < m; ++j)
            scanf("%d", &mp[i][j]);
    if(m == 2) {
        dp[1][0][oo] = dp[1][0][ox] = dp[1][0][xo] = dp[1][0][xx] = 0;
        dp[1][1][oo] = 0;
        dp[1][1][ox] = mp[1][1];
        dp[1][1][xo] = mp[1][0];
        dp[1][1][xx] = mp[1][1] + mp[1][0];
        for(register int j = 1; j <= k; ++j)
                printf("%d %d, oo : %d xx : %d xo : %d ox : %d\n", 1, j, dp[1][j][oo], dp[1][j][xx], dp[1][j][xo], dp[1][j][ox]);
        for(register int i = 2; i <= n; ++i) {
            for(register int j = 1; j <= k; ++j)    {
                if(j) {
                    tmp[0][oo] = dp[i - 1][j - 1][oo];
                    tmp[0][xx] = dp[i - 1][j - 1][xx];
                    tmp[0][xo] = dp[i - 1][j - 1][xo];
                    tmp[0][ox] = dp[i - 1][j - 1][ox];
                }else
                tmp[0][oo] = tmp[0][xx] = tmp[0][xo] = tmp[0][ox] = -inf;
                
                tmp[1][oo] = dp[i - 1][j][oo];
                tmp[1][xx] = dp[i - 1][j][xx];
                tmp[1][xo] = dp[i - 1][j][xo];
                tmp[1][ox] = dp[i - 1][j][ox];
                dp[i][j][oo] = max(max(tmp[1][oo], 
                                       tmp[1][xx]),
                                   max(tmp[1][ox], 
                                       tmp[1][xo]));
                dp[i][j][xx] = max(max(tmp[0][oo], 
                                       tmp[1][xx]),
                                   max(tmp[0][ox], 
                                       tmp[0][xo])) + mp[i][0] + mp[i][1];
                dp[i][j][ox] = max(max(tmp[0][oo], 
                                       tmp[0][xx]),
                                   max(tmp[1][ox], 
                                       tmp[0][xo])) + mp[i][1];
                dp[i][j][xo] = max(max(tmp[0][oo], 
                                       tmp[0][xx]),
                                   max(tmp[0][ox], 
                                       tmp[1][xo])) + mp[i][0];
            }
            for(register int j = 1; j <= k; ++j)
                printf("%d %d, oo : %d xx : %d xo : %d ox : %d\n", i, j, dp[i][j][oo], dp[i][j][xx], dp[i][j][xo], dp[i][j][ox]);
        }
        for(register int i = 0; i <= k; ++i)
            mx = max(mx, max(max(dp[n][k][oo], dp[n][k][xx]), max(dp[n][k][ox], dp[n][k][xo])));
        printf("%d\n", mx);
        return 0;
    }
    dp[1][1][xo] = mp[1][0];
    for(register int i = 2; i <= n; ++i) {
        for(register int j = 1; j <= k; ++j)    {
            if(j) {
                tmp[0][oo] = dp[i - 1][j - 1][oo];
                tmp[0][xo] = dp[i - 1][j - 1][xo];
            }else {
                tmp[0][oo] = tmp[0][xo] = -inf;
            }
            tmp[1][oo] = dp[i - 1][j][oo];
            tmp[1][xo] = dp[i - 1][j][xo];
            dp[i][j][oo] = max(tmp[1][oo], tmp[1][xo]);
            dp[i][j][xo] = max(tmp[0][oo], tmp[1][xo]) + mp[i][0];
            mx = max(mx, max(dp[i][j][xo], dp[i][j][oo]));
        }
        for(register int j = 0; j <= k; ++j)
                printf("%d %d, oo : %d xx : %d xo : %d ox : %d\n", i, j, dp[i][j][oo], dp[i][j][xx], dp[i][j][xo], dp[i][j][ox]);
    }
    printf("%d\n", mx);
    return 0;
}