interestingLSY 的博客

interestingLSY 的博客

题解 P2331 【[SCOI2005]最大子矩阵】

posted on 2018-10-23 14:57:32 | under 题解 |

此篇题解为下面几篇的小优化(如何把代码写短)请先阅读透其他题解之后再来qwq

咳咳,思路楼下(楼上?)的dalao已经说得非常好了。

只不过。。。您们的代码好长啊!!!

那么在这里,我将介绍,怎么写出一份短小精悍的代码

话不多说,先上菜(下面有讲解

#include <bits/stdc++.h>
using namespace std;
#define rg register
#define INF 0x3f3f3f3f
#define max(a,b) ((a)>(b)?(a):(b))
#define Mymax(a,b) ((a)=max(a,b))
#define Msn(a,x) memset(a,x,sizeof a)
#define For(i,j) for( rg int (i) = 1 ; (i) <= (j) ; ++(i) )
#define For0(i,j) for( rg int (i) = 0 ; (i) < (j) ; ++(i) )
////////////////////////////////////////////////////////////////////////////
////////////////////////////////////////////////////////////////////////////
#define MAXN 110
#define MAXM 4
#define MAXK 12
const int Tran[6][6] = {
    {0,0,0,0,0},
    {1,0,1,1,0},
    {1,1,0,1,0},
    {1,1,1,0,2},
    {2,1,1,2,0}
};
const int sel[6][3] = {
    {0,0},
    {1,0},
    {0,1},
    {1,1},
    {1,1}
};

int n,m,k;
int a[MAXN][MAXM];

int mem[MAXN][MAXK][6];
#define NOW mem[pos][used][stat]
int Dfs( int pos , int used , int stat ){
    if( used + Tran[stat][0] > k ) return -INF;
    if( pos == n+1 ) return 0;
    if( NOW != -1 ) return NOW; // 记忆化

    int ans = -INF;
    For0(ns,5){
        int tans = Dfs(pos+1,used+Tran[stat][ns],ns) + sel[ns][0]*a[pos][1] + sel[ns][1]*a[pos][2];
        Mymax(ans,tans);
    }

    return NOW = ans;
}

int main(){
    Msn(mem,-1);

    cin >> n >> m >> k;
    For(i,n)
        For(j,m)
            cin >> a[i][j];

    int ans = Dfs(1,0,0);
    cout << ans << endl;

    return 0;
}

哇好短啊

参照楼下的思路,我们的stat表示上一列的状态

  • 0 空出这一行

  • 1 选择左边空出右边

  • 2 选择右边空出左边

  • 3 选择这一行两个(两个一块作为一个矩阵的一部分)

  • 4 选择这一行两个(不作为一个矩阵,而是左边一列单独一个矩阵,右边单独一个矩阵)

(这是楼下的思路,同时请注意状态3,4的顺序有所不同

那么需要分类讨论吗?不用!

其实,核心就是两个二维数组(矩阵?)—— $Tran$ 和 $Sel$

  • $Tran_{i,j}$ 记录从状态 $i$ 到状态 $j$ ,需要 “截止” 当前多少矩阵(我在dp时, $used$ 中不包含当前还没截止的矩阵

  • $Sel_{i,j}$ 记录状态 $i$ 是否选第 $j+1$ 列(数组下标从0开始)

所以,转移的时候直接从 $Dfs(pos,used,stat)$ 转移到 $Dfs(pos+1,used+Tran_{stat,newstat},newstat)$ 即可!

但是我们怎么判断当前状态是否超出了 “只能选k个” 的限制?

直接在递归调用时判断,当然会很麻烦。

那怎么办?直接给下一波dfs判断就行!具体的,判断 $Tran_{stat,0}+used$ 是不是小于等于 $k$ !