首页 > 代码库 > 【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—局部极小值
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。