为了达到 n^3 而不是 n^4 复杂度，我们只枚举想要的右下角，以及最优矩阵的左上角的 x 坐标，将满足要求的最优矩阵存为 f_{i,j,k} （i, j 表示右下角，k 表示左上角的 x 坐标）
转移过程和最大字段和很像，每次决策是否将这最后以行接在上一行后面，还是这单独一行另起一个矩阵。
\begin{aligned}
f_{i, j, k} = \max(f_{i, j, k - 1}, 0) + val_{i, j} - val_{k - 1, j}
\end{aligned}
有了最大子矩阵接下来的过程就比较简单了，细节代码里有很多注释。
## Code
我代码里写的稍微有些不同，最后一步枚举的不是第一个的右下，而是第二个的左上，但是过程基本一样。
```cpp
/*
最大子矩阵 is acutally a little more complicated then I thought,
we need 2 dps for max sub matrix with a fixed bottom right,
and 2 more for such with fixed top left
let's use bottom right as example
first for max subarray(substring), each time the decision we make
with dp is whether to connect with last i - 1, or to start new.
similar here, this time however, 2 dimentional
the key to achieving n^3 not n^4 complexity is that we only
enumerate the coordinate of bottom right(duh, we need that), and
the x(or y if you want) coordinate of the top left of the max
submatrix. what about y? well now we get to use dp and just
decide whether we connect this last row to the matrix above or
just to start a new one with height 1(just this row).
be careful though we need 2 dp arrays, one 3d and one 2d, cuz
2d store answer, but then actually transfering we need to
restrict which j we transfer from, which need to be specified in
the state.(see details in code)also I don't actually have to make
it 3d cuz i can just put j as outer most layer loop. but you
know, we've got space!
brm[i][j] = the max br[k][l] for all k <= i and l <= j
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n, k, dif[205][205], pre[205][205];
int ans, orig, op1[205][205], op2[205][205], cnt, chec;
int brf[205][205][205], tlf[205][205][205];
int br[205][205], tl[205][205], brm[205][205];
//这里的一大堆数组，brf就是题解里的f数组，br是对于一对 i, j 所有
//k 找到最优的后存起来了，tl同理，只不过是左上角
//brm 则是在最后需要找到在一个点一下的所有 br 里最大的一个
//相当于一个二维后缀最大值
int mx, my;
signed main(){
cin>>n>>k;
for(int i = 1; i <= n; i++){
int x, y, x2, y2;
cin>>x>>y>>x2>>y2;
x++, y++, x2++, y2++;
dif[x][y]++;
dif[x][y2]--;
dif[x2][y]--;
dif[x2][y2]++;
mx = max(mx, x2);
my = max(my, y2);
//start from 1 instead of 0, so we don't have RE
}
mx = min(mx, 200LL);
my = min(my, 200LL);
//MAJOR MAJOR BUG!!!!!!!!
//cuz our br will consider the border cell painted, but cells
//at 200(or 201 now that we've added 1) doesn't exist! it's
//just a line, there's no cells behind the line
//this stuck me for 50 minutes, and even after discovering
//this bug I wrote max() instead of min, and stuck me another
//10 minutes.
for(int i = 1; i <= mx; i++){
for(int j = 1; j <= my; j++){
pre[i][j] = dif[i][j];
pre[i][j] += pre[i - 1][j]+pre[i][j-1]-pre[i-1][j-1];
if(pre[i][j] == k)orig++;
}
}
//found prefix sum(silver level end here)
//ans right now is the answer for adding no rectangles
//one dimentional prefix sum TOP TO BOTTOM!!!!
for(int i = 1; i <= mx; i++){
for(int j = 1; j <= my; j++){
op1[i][j] = op1[i - 1][j] + (pre[i][j] == (k - 1));
op1[i][j] -= (pre[i][j] == (k));
}
}
for(int i = 1; i <= mx; i++){
for(int j = 1; j <= i; j++){
for(int k = 1; k <= my; k++){
//bottom right corner is i, k
int lyc = max(brf[i][j][k - 1], 0LL);
//last y coordinate(when y was k - 1)
/*
if(lyc+op1[i][k]-op1[j-1][k] == 7 && i == mx && k == 3){
cout<<mx<<" "<<j<<endl;
}
//bro above was actually a bug cuz I forgot to
//comment it off, like out of all these years
//of programming, this?!?!?!
*/
brf[i][j][k] = lyc + op1[i][k] - op1[j - 1][k];
//we still enumerate the x coordinate of the
//top left of the best rectange with bottom right
//i k, but we don't need to enumerate the y
//coordinate cuz we use dp
br[i][k] = max(br[i][k], brf[i][j][k]);
//we had to add a dimension for brf cuz other
//wise we might choose an L shape around the
//negatives, so we have to limit the js we can
//transfer brf from
}
}
}
//now, we've (finally) found the biggest rectangle with
//bottom right at i, j, stored in br[i][j]
//this time BOTTOM TO TOP!!!!
for(int i = mx; i >= 1; i--){
for(int j = 1; j <= my; j++){
op2[i][j] = op2[i + 1][j];
op2[i][j] += (pre[i][j] == (k - 1));
op2[i][j] -= (pre[i][j] == (k));
}
}
for(int i = mx; i >= 1; i--){
for(int j = mx; j >= i; j--){
for(int k = my; k >= 1; k--){
int lyc = max(tlf[i][j][k + 1], 0LL);
//this is actually basically the decision making
//process of dp
tlf[i][j][k] = lyc + op2[i][k] - op2[j + 1][k];
tl[i][k] = max(tl[i][k], tlf[i][j][k]);
}
}
}
for(int i = 1; i <= mx; i++){
for(int j = 1; j <= my; j++){
brm[i][j] = br[i][j];
brm[i][j] = max(brm[i][j - 1], brm[i][j]);
brm[i][j] = max(brm[i - 1][j], brm[i][j]);
}
}
ans = orig;
for(int i = 1; i <= mx; i++){
for(int j = 1; j <= my; j++){
//i, j as the top left of the second rectangle
ans = max(ans, orig + tl[i][j]);
ans = max(ans, orig + br[i][j]);
int mabr = max(brm[i - 1][my], brm[mx][j - 1]);
//don't forget to do i - 1 and j - 1 not i and j, cuz
//both br and tl claim the block at their border
//if we do i,j we have a row overlapping
ans = max(ans, orig + mabr + tl[i][j]);
}
}
cout<<ans<<endl;
return 0;
}
```
## After thought
好题呀，建议升紫。
求赞。