首页 > 代码库 > 【bzoj2669】 cqoi2012—局部极小值

【bzoj2669】 cqoi2012—局部极小值

http://www.lydsy.com/JudgeOnline/problem.php?id=2669 (题目链接)

题意

  给出一个$n*m$的整数矩阵,其中$[1,nm]$中的整数每个出现一次,有一些位置为局部最小值。问方案数。

Solution

  好神的dp啊。

  http://blog.csdn.net/popoqqq/article/details/48028773

  $cnt_j$表示的是,在局部最小值被填充的状态为$j$的情况下,目前有多少个位置可以填,这些位置中包括已经被填了数的位置。

细节

  最后加模再取模

代码

// bzoj2669#include<algorithm>#include<iostream>#include<cstdlib>#include<cstring>#include<cstdio>#include<cmath>#define LL long long#define inf (1ll<<30)#define MOD 12345678#define Pi acos(-1.0)#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);using namespace std;int xx[9]={0,-1,-1,-1,0,1,1,1,0};int yy[9]={1,1,0,-1,-1,-1,0,1,0};int f[30][1000],cnt[1000],fil[10][10],bin[30],ans,n,m;pair<int,int> t[10];char s[10][10];int dp() {	memset(f,0,sizeof(f));	memset(cnt,0,sizeof(cnt));	int top=0;	for (int i=1;i<=n;i++)		for (int j=1;j<=m;j++) if (s[i][j]==‘X‘) t[++top]=pair<int,int>(i,j);	for (int i=0;i<bin[top];i++) {		memset(fil,0,sizeof(fil));		for (int j=1;j<=top;j++) if (!(i&bin[j-1])) fil[t[j].first][t[j].second]=1;		for (int j=1;j<=n;j++)			for (int l,k=1;k<=m;k++) {				for (l=0;l<9;l++) if (fil[j+xx[l]][k+yy[l]]) break;				if (l==9) cnt[i]++;			}	}	f[0][0]=1;	for (int i=1;i<=n*m;i++)		for (int j=0;j<bin[top];j++) {			(f[i][j]+=f[i-1][j]*max(0,cnt[j]-i+1))%=MOD;			for (int k=1;k<=top;k++)				if (bin[k-1]&j) (f[i][j]+=f[i-1][j^bin[k-1]])%=MOD;		}	return f[n*m][bin[top]-1];}void dfs(int x,int y,int c) {	if (x==n+1) {(ans+=dp()*(c&1 ? -1 : 1))%=MOD;return;}	if (y==m) dfs(x+1,1,c);	else dfs(x,y+1,c);	int k;	for (k=0;k<9;k++) if (s[x+xx[k]][y+yy[k]]==‘X‘) break;	if (k==9) {		s[x][y]=‘X‘;		if (y==m) dfs(x+1,1,c+1);		else dfs(x,y+1,c+1);		s[x][y]=‘.‘;	}}int main() {	bin[0]=1;for (int i=1;i<=20;i++) bin[i]=bin[i-1]<<1;	scanf("%d%d",&n,&m);	for (int i=1;i<=n;i++) scanf("%s",s[i]+1);	for (int i=1;i<=n;i++)		for (int j=1;j<=m;j++)			if (s[i][j]==‘X‘)				for (int k=0;k<8;k++) if (s[i+xx[k]][j+yy[k]]==‘X‘) {puts("0");return 0;}	dfs(1,1,0);	printf("%d\n",(ans+MOD)%MOD);	return 0;}

 

【bzoj2669】 cqoi2012—局部极小值