补完这道C题感觉收益匪浅啊…也学习到了优化n^4前缀和的技巧，感觉和之先做过的多维背包DP很类似：
首先把行，列，和整个的前缀和预处理出来
然后封装函数calc计算固定上界和下界时，某一列中符合要求的数量，如列y：
然后写一个计算如图形状中，需要反转的数量的计算函数get;
变成像一个汉堡一样，上界下界全是1，中间全是0的如图形状需要反转的次数
然后我们就可以开始分析了；
我们列出当确定上界up,下界dw,右界i的时候，（这些靠枚举），如何求得符合要求的传送门？
借助我们之先封装好的两个函数，有：
g
e
t
(
u
p
,
1
,
d
w
,
i
−
1
)
−
g
e
t
(
u
p
,
1
,
d
w
,
i
−
3
)
+
c
a
l
c
(
u
p
,
d
w
,
i
−
3
)
+
c
a
l
c
(
u
p
,
d
w
,
i
)
get(up,1,dw,i-1)-get(up,1,dw,i-3)+calc(up,dw,i-3)+calc(up,dw,i)
get(up,1,dw,i−1)−get(up,1,dw,i−3)+calc(up,dw,i−3)+calc(up,dw,i)
我们讲中间两项加个括号发现：
g
e
t
(
u
p
,
1
,
d
w
,
i
−
1
)
+
c
a
l
c
(
u
p
,
d
w
,
i
)
−
[
g
e
t
(
u
p
,
1
,
d
w
,
i
−
3
)
−
c
a
l
c
(
u
p
,
d
w
,
i
−
3
)
]
get(up,1,dw,i-1)+calc(up,dw,i)-[get(up,1,dw,i-3)-calc(up,dw,i-3)]
get(up,1,dw,i−1)+calc(up,dw,i)−[get(up,1,dw,i−3)−calc(up,dw,i−3)]
我们发现中括号内的所有参数只和我们枚举的右边界有关，即我们依次从左往右枚举右边界的时候，这个答案会不断地更新，我们每次取最大值即可（因为减去最大就是最小值），这样就省去了枚举左边界了
因此我们令mx=-0x3f3f3f3f;
然后每次更新这个mx：
m
x
=
m
a
x
(
m
x
,
[
g
e
t
(
u
p
,
1
,
d
w
,
i
−
3
)
−
c
a
l
c
(
u
p
,
d
w
,
i
−
3
)
]
)
mx=max(mx,[get(up,1,dw,i-3)-calc(up,dw,i-3)])
mx=max(mx,[get(up,1,dw,i−3)−calc(up,dw,i−3)])
最终的时间复杂度是n^3
#include<bits/stdc++.h>
using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define N 410
//================================
typedef pair<int,int> pii;
#define x first
#define y second
typedef long long LL; typedef unsigned long long ULL; typedef long double LD;
inline LL read() { LL s = 0, w = 1; char ch = getchar(); for (; !isdigit(ch); ch = getchar()) if (ch == '-') w = -1; for (; isdigit(ch); ch = getchar()) s = (s << 1) + (s << 3) + (ch ^ 48); return s * w; }
inline void print(LL x, int op = 10) { if (!x) { putchar('0'); if (op) putchar(op); return; } char F[40]; LL tmp = x > 0 ? x : -x; if (x < 0)putchar('-'); int cnt = 0; while (tmp > 0) { F[cnt++] = tmp % 10 + '0'; tmp /= 10; } while (cnt > 0)putchar(F[--cnt]); if (op) putchar(op); }
//=================================
int T;
int n,m,g[N][N],cnt;
int row[N][N],col[N][N],s[N][N],res=0x3f3f3f3f;
int calc(int x1,int x2,int y){
int ret = (x2-x1-1) - (row[x2-1][y] - row[x1][y]);
return ret;
}
int get(int x1,int y1,int x2,int y2){
int ret = s[x2-1][y2] - s[x1][y2] - s[x2-1][y1-1] + s[x1][y1-1];
ret += 2*(y2-y1+1) - (col[x1][y2] - col[x1][y1-1]) - (col[x2][y2] - col[x2][y1-1]);
return ret;
}
void pre_work(){
memset(g,0,sizeof g);
memset(row,0,sizeof 0);
memset(col,0,sizeof 0);
memset(s,0,sizeof 0);
res=0x3f3f3f3f;
n=read(),m=read();
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++){
char c;
cin >> c;
g[i][j] = (c=='1');
}
//pre_row
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
col[i][j]=col[i][j-1]+g[i][j];
//pre_col
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
row[i][j]=row[i-1][j]+g[i][j];
//all
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
s[i][j]=s[i-1][j]+s[i][j-1]-s[i-1][j-1]+g[i][j];
}
void solve(){
int res=0x3f3f3f3f;
for(int up=1;up+4<=n;up++) //枚举up边界
for(int dw=up+4;dw<=n;dw++){ //枚举down边界
int mx=-0x3f3f3f3f;
for(int i=4;i<=m;i++){ //枚举you边界
mx=max(mx,get(up,1,dw,i-3)-calc(up,dw,i-3));
res=min(res,get(up,1,dw,i-1)+calc(up,dw,i)-mx);
}
}
print(res);
}
//=================================
int main(){
T=read();
while(T--){
pre_work();
solve();
}
return 0;
}