BZOJ 2669 局部极小值&JZOJ.4700 Garden

Problem

本题出自CQOI2012，BZOJ2669。 题目网址：http://www.lydsy.com/JudgeOnline/problem.php?id=2669

Description

Input

Output

Sample Input

2 3 2 X. .. .X 2 2 X. ..

Sample Output

60 6

Data Constraint

Solution

我们可以发现，矩阵里最多出现8个’X’，所以我们可以状压DP。 首先预处理一个Rest数组，Rest[s] (s是2进制数)表示位置为X的点的填充状态为s时，可以放数的位置个数(包括位置为X的点)。 那么我们可以得出DP方程：(k比s少一位2进制位)

F[i][s]=Σk∈sF[i−1][k]+F[i−1][s]∗(Rest[i]−(i−1)) . 但是，我们发现这样一种情况： 所以，如果有出现一种是’.’的格子，且周围全是’.’，那么我们要暴力，适当的将这些’.’改为’X’.求出所有当X有奇数个的时候加上DP后的结果；偶数个的时候减去DP后的结果。 注意特殊情况特判。

Code

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #define N 10 #define mo 12345678 #define fo(i,a,b) for(i=a;i<=b;i++) const int fx[8][2]={{-1,-1},{-1,0},{-1,1},{0,-1},{0,1},{1,-1},{1,0},{1,1}}; int _,n,m,i,j,k,l,od,s; int _2[12],a[N][N],b[30][2],bz[N][N],f[N*N][1000],rest[1000]; char c[N][N]; long long ans; int dp() { int tot=0,S=0; fo(i,1,n) fo(j,1,m) if (c[i][j]=='X') { S+=_2[++tot]; b[tot][0]=i; b[tot][1]=j; } fo(i,0,S) { od++; rest[i]=0; fo(j,1,tot) if ((_2[j]&i)==0) { bz[b[j][0]][b[j][1]]=od; fo(k,0,7) bz[b[j][0]+fx[k][0]][b[j][1]+fx[k][1]]=od; } fo(j,1,n) fo(k,1,m) if (bz[j][k]!=od) rest[i]++; } memset(f,0,sizeof(f)); f[0][0]=1; fo(i,1,n*m) fo(s,0,S) { f[i][s]=(f[i][s]+f[i-1][s]*(rest[s]-i+1)%mo)%mo; fo(j,1,tot) if ((_2[j]&s)>0) f[i][s]=(f[i][s]+f[i-1][s-_2[j]])%mo; } return f[n*m][_2[tot+1]-1]; } void dg(int x,int y,int z) { int sum; if (x>n) { sum=dp()*z; ans=(ans+sum+mo)%mo; return; } if (y==m) dg(x+1,1,z);else dg(x,y+1,z); bool p=0; int xx,yy; fo(i,0,7) { xx=x+fx[i][0]; yy=y+fx[i][1]; if (c[xx][yy]=='X') { p=1; break; } } if (!p && c[x][y]!='X') { c[x][y]='X'; if (y==m) dg(x+1,1,-z);else dg(x,y+1,-z); c[x][y]='.'; } } int main() { _2[1]=1; fo(i,2,10) _2[i]=_2[i-1]*2; scanf("%d",&_); while (_--) { memset(a,127,sizeof(a)); memset(c,0,sizeof(c)); scanf("%d%d",&n,&m); scanf("\n"); l=0; fo(i,1,n) { fo(j,1,m) { scanf("%c",&c[i][j]); if (c[i][j]=='.') l++; } scanf("\n"); } if (l==n*m) { printf("0\n"); continue; } bool p1=0; fo(i,1,n) { fo(j,1,m) if (c[i][j]=='X') { fo(k,0,7) if (c[i+fx[k][0]][j+fx[k][1]]=='X') { p1=1; break; } if (p1) break; } if (p1) break; } if (p1) { printf("0\n"); continue; } ans=0; dg(1,1,1); printf("%lld\n",(ans+mo*10)%mo); } }

——2016.8.16