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

## 此篇题解为下面几篇的小优化（如何把代码写短）请先阅读透其他题解之后再来qwq 咳咳，思路楼下（楼上？）的dalao已经说得非常好了。 只不过。。。您们的代码好长啊！！！ ### 那么在这里，我将介绍，怎么写出一份**短小精悍**的代码 话不多说，先上菜（下面有讲解 ```cpp #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$!