何意味

首先我们可以尝试处理出所有可以被选择的矩形 并将有冲突的连边

由于$1,2,3$互不相同 所以容易证明建出来的是二分图

我们要求最大独立集 转化为最大匹配 由于每个点连的边不多，所以用dinic可以很快地解决

但是 dinic要建$O(nm)$条边 拼尽全力也没有把空间卡过去T^T

所以我们尝试用另一种方法求最大匹配 这里我贪心地枚举当前行$i$，从左到右枚举横矩形 再枚举开头在第$(i-2)$行的的竖矩形 自上而下匹配

至于正确性 我们发现此时第$(i-2)$行的竖矩形可能匹配到的横矩形都已经被枚举 而自上而下是因为开头更靠下的竖矩形无法匹配开头更靠上的横矩形 因此让竖矩形尽可能匹配所在行更接近自己的横矩形最优

复杂度$O(nm)$

#include<bits/stdc++.h>
using namespace std;
const int mod=1e9+7,inf=1e9;
int n,m;
short a[5050][5050];
int vis[4][5050];//覆盖当前点的横矩形编号 滚动数组 
int idx;
int dld[25010000];//该矩形是否已经被匹配 
int ans=0;//匹配数  
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
//	freopen("ex.in","r",stdin);
//	freopen("my.out","w",stdout);
//	system("fc my.out ex.out");return 0;
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		string s;
		cin>>s;
		for(int j=1;j<=m;j++){
			a[i][j]=s[j-1]-'0';
		}
	}
	for(int i=1;i<=n;i++){
		for(int j=1;j<=m-2;j++){
			if(a[i][j]==1&&a[i][j+1]==2&&a[i][j+2]==3){
				++idx;
				vis[3][j+1]=vis[3][j+2]=vis[3][j]=idx;
			}
		}
		if(i>=3){
			for(int j=1;j<=m;j++){
				if(a[i-2][j]==1&&a[i-1][j]==2&&a[i][j]==3){
					++idx;
					if(vis[1][j]&&dld[vis[1][j]]==0){
						dld[vis[1][j]]=1;
						ans++;
					}
					else if(vis[2][j]&&dld[vis[2][j]]==0){
						dld[vis[2][j]]=1;
						ans++;
					}
					else if(vis[3][j]&&dld[vis[3][j]]==0){
						dld[vis[3][j]]=1;
						ans++;
					}
				}
			}
		}
		for(int j=1;j<=m;j++){
			vis[1][j]=vis[2][j];
			vis[2][j]=vis[3][j];
			vis[3][j]=0;
		}
	}
	cout<<idx-ans;
	return 0;
}

洛谷 P7668 [JOI 2018 Final] 团子制作 / Dango Maker