「USACO 2021 US Open Platinum」Balanced Subsets

「USACO 2021 US Open Platinum」Balanced Subsets

考虑题目给出的定义对应怎样的图形，显然是一个凸的封闭图形

不妨通过左右边线描述，

1.左边线先左移再右移

2.右边线先右移再左移

不妨直接令(dp_{i,l,r,f1,f2})表示当前第(i)行，当前左右边线为(l,r(lleq r,forall jin[l,r],a_{i,j}=G))

(f1,f2)表示当前左右边线处于左移还是右移状态

以左边线为例，定义右移开始的时刻为第一个(l>l')的时刻

容易得到转移，是一个前/后缀和的形式

那么对于([l,r])两维分别做前缀和，然后(O(n^3))转移即可

注意转移过程中要确保([l',r'],[l,r])有交

以下是暴力二维前缀和+手艹9种转移的代码

const int N=170,P=1e9+7;

int n;
int c[N];
char s[N];
int dp[N][N][2][2];
int F[N][N][2][2];
int S(int a,int b,int x1,int x2,int y1,int y2){
	x1--,y1--;
	return (0ll+F[x2][y2][a][b]-F[x1][y2][a][b]-F[x2][y1][a][b]+F[x1][y1][a][b])%P;
}

int main(){
	n=rd();
	int ans=0;
	rep(i,1,n) {
		scanf("%s",s+1);
		rep(j,1,n) c[j]=c[j-1]+(s[j]=='G');
		memset(F,0,sizeof F);
		rep(i,1,n) rep(j,1,n) rep(a,0,1) rep(b,0,1) {
			F[i][j][a][b]=(0ll+F[i-1][j][a][b]+F[i][j-1][a][b]-F[i-1][j-1][a][b]+dp[i][j][a][b])%P;
		}
		memset(dp,0,sizeof dp);
		rep(l,1,n) rep(r,l,n) if(c[r]-c[l-1]==r-l+1) {
			(dp[l][r][0][0]+=S(0,0,l,r,l,r))%=P;
			(dp[l][r][1][0]+=S(0,0,1,l-1,l,r))%=P;
			(dp[l][r][0][1]+=S(0,0,l,r,r+1,n))%=P;
			(dp[l][r][1][1]+=S(0,0,1,l-1,r+1,n))%=P;
	
			(dp[l][r][0][1]+=S(0,1,l,r,r,n))%=P;
			(dp[l][r][1][1]+=S(0,1,1,l-1,r,n))%=P;
			
			(dp[l][r][1][0]+=S(1,0,1,l,l,r))%=P;
			(dp[l][r][1][1]+=S(1,0,1,l,r+1,n))%=P;
			
			(dp[l][r][1][1]+=S(1,1,1,l,r,n))%=P;
		}
		rep(l,1,n) rep(r,l,n) if(c[r]-c[l-1]==r-l+1) dp[l][r][0][0]++;
		rep(l,1,n) rep(r,l,n) rep(a,0,1) rep(b,0,1) if(dp[l][r][a][b]) 
			ans=(ans+dp[l][r][a][b])%P;
	}
	Mod2(ans),printf("%d
",ans);
}