Codeforces #745 div2 C. Portal

补完这道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

using namespace std;
//================================
#define debug(a) cout << #a": " << a << endl;
#define N 410
//================================
typedef pair 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;
}