求贪心正确性证明或hack

如题。

贪心策略为对于一个对角线上的有交的冲突集合，从上往下枚举，每次若出现冲突对，则将答案加一，然后忽略这个冲突对的横和竖方案的影响。每次取的横和竖的冲突对一定是三个点中行坐标最小的点最小的两个。

代码实现为先把竖线标记出来，然后正常扫点，每遇到一个横线方案就将答案加一，然后把这个横线覆盖的行坐标最小的竖线取消标记。最后所有横线扫完后，再将答案加上网格上剩下没有被取消标记的竖线数量。

代码如下。

CPP

#include<bits/stdc++.h>
#define ll long long
using namespace std;
template<typename T> inline void read(T &x){
	T w=1;
	x=0;
	char c=getchar();
	while(!isdigit(c)){
		if(c=='-') w=-1;
		c=getchar();
	}
	while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
	x*=w;
}
template<typename T> inline void write(T x){
	if(x<0) putchar('-'),x=(~x)+1;
	if(x>9) write(x/10);
	putchar(x%10^48);
}
const int N=3e3+10,inf=1e9;
char c[N][N];
int n,m,cnt,id[N][N];
int Min(int h,int x,int y){
	return id[h][x]>id[h][y] ? y : x;
}
int main(){
//	freopen("jiaozi.in","r",stdin);
//	freopen("jiaozi.out","w",stdout);
	read(n),read(m);
	for(int i=1;i<=n;i++){
		scanf("%s",c[i]+1);
		for(int j=1;j<=m;j++) id[i][j]=inf;
	}
//	for(int i=1;i<=n;i++){
//		for(int j=1;j<=m;j++) cout<<c[i][j];
//		cout<<"\n";
//	}
	for(int i=3;i<=n;i++){
		for(int j=1;j<=m;j++){
			if(c[i-2][j]=='R'&&c[i-1][j]=='G'&&c[i][j]=='W') id[i-2][j]=id[i-1][j]=id[i][j]=++cnt;
		}
	}
	int ans=0,k=0;
	for(int i=1;i<=n;i++){
		for(int j=3;j<=m;j++){
			if(c[i][j-2]=='R'&&c[i][j-1]=='G'&&c[i][j]=='W'){
				int t=j-2;
				t=Min(i,t,j-1);
				t=Min(i,t,j);
				ans++;
				if(id[i][t]!=inf){
					k++;
					if(c[i][t]=='R') id[i][t]=id[i+1][t]=id[i+2][t]=inf;
					else if(c[i][t]=='G') id[i-1][t]=id[i][t]=id[i+1][t]=inf;
					else if(c[i][t]=='W') id[i-2][t]=id[i-1][t]=id[i][t]=inf;
				}
			}
		}
	}
	ans+=cnt-k;
	write(ans);
	return 0;
}
/*
最多只有3格…

相交的情况是固定的

现在考虑贪心地取这种序列

不会。 
*/

求贪心正确性证明或hack

讨论操作

回复

相关推荐

求贪心正确性证明或hack