2669: [cqoi2012]局部極小值

Time Limit:?3 Sec??Memory Limit:?128 MB
Submit:?561??Solved:?293
[Submit][Status][Discuss]

Description

有一個n行m列的整數矩陣，其中1到nm之間的每個整數恰好出現一次。如果一個格子比所有相鄰格子（相鄰是指有公共邊或公共頂點）都小，我們說這個格子是局部極小值。 給出所有局部極小值的位置，你的任務是判斷有多少個可能的矩陣。

Input

輸入第一行包含兩個整數n和m（1<=n<=4, 1<=m<=7），即行數和列數。以下n行每行m個字符，其中“X”表示局部極小值，“.”表示非局部極小值。

Output

輸出僅一行，為可能的矩陣總數除以12345678的余數。

Sample Input

3 2
X.
..
.X

Sample Output

60

HINT

Source

Solution

這道題有點勁！自己沒想出來，于是看的論文 ?傳送門? ?下面引用論文里的題解

對于一個合法的數填寫方案，其中的數放置的順序對其是沒有影響的，于是我們可以從1開始填數，并且一個一個地填進格子。如果采取這樣的做法，那么所有的“X”必然要在其周邊所有的格子填數之前就填好一個數，而"X"有多少呢？很顯然最多只有8個而已。這時我們就可以想到這樣的一個狀態壓縮方式：opt[i][j]（j是一個二進制表達）表示的是i及其以后的數還沒有填進格子，被填寫了數的“X”集合狀態為j的情況下的方案數。

如上圖4*7的矩陣中，紅色的"X"表示已經填寫數的"X"，紅色的格子表示已經填寫數的非"X"格子，那么可以表述成這樣的狀態opt[8][num]（8表示已經填寫了7個數，下一個填寫8，num是011010的表示，含義是第2、3、5個"X"已經填寫了數了）

如果我們轉移的話就會有兩種情況：

第一種情況就是把i填進一個"X"中，這個顯然只要枚舉一下放哪一個"X"，然后把這個"X"加入j表示的集合里就可以了。

?

如上圖，下一步我們填寫"X"是可以隨意的，因為只要存在解，任意的"X"都是互不影響的。當前的狀態為f[8][num1]（num1為011010的表示），可以推導到f[9][num2](num2為111010、011110、011011的表示)。

第二種情況就是把i填進一個非"X"中，這樣的選擇就有很多了。對于全圖我們一共有n*m個格子，若沒有填進去數的"X"格子以及其周邊的格子共有tot個，顯然這tot個格子都是不能填i的（因為填進的是一個非"X"，并且一個沒有填進去數的"X"格子其周邊因為都要比它小，所以這兩者都不可以填i），又因為已經填寫了1到i-1所有的數，所以剩下能填的選擇數就是n*m-tot-(i-1)。

?

如上圖，所有的藍色區域都是無法填寫i的，而下一步能填寫的格子就只有白色的格子，即4*7-17-7=4個格子。

由于這樣的處理方式，尤其是第二種轉移可能會導致非"X"點變為最小值，所以還需要使用容斥原理來解決。

Code

#include<iostream> #include<cstdio> #include<cstring> #include<cmath> #include<algorithm> using namespace std; #define LL long long #define P 12345678 int N,M,ANS,bin[11],f[100][256],cnt[256]; char mp[10][10]; int dx[10]={-1,-1,-1,0,0,0,1,1,1,0},dy[10]={-1,0,1,-1,0,1,-1,0,1,0}; inline bool OK(int x,int y) {return x>=1 && x<=N && y>=1 && y<=M;} #define Pa pair<int,int> Pa stack[100]; int top; bool visit[10][10]; inline void PreWork() {top=0;for (int i=1; i<=N; i++)for (int j=1; j<=M; j++)if (mp[i][j]=='X') stack[top++]=make_pair(i,j);for (int i=0; i<bin[top]; i++){cnt[i]=0; memset(visit,0,sizeof(visit));for (int j=0; j<top; j++) if (~i&bin[j]) visit[stack[j].first][stack[j].second]=1;for (int j=1; j<=N; j++)for (int k=1; k<=M; k++)if (!visit[j][k]){bool flag=1;for (int d=0,x,y; d<=8 && flag; d++) x=j+dx[d],y=k+dy[d],flag=!visit[x][y];cnt[i]+=flag;}} } inline int DP() {PreWork();memset(f,0,sizeof(f));f[0][0]=1;for (int i=1; i<=N*M; i++)for (int j=0; j<bin[top]; j++){for (int k=0; k<top; k++)if (j&bin[k]) (f[i][j]+=f[i-1][j^bin[k]])%=P;(f[i][j]+=(LL)f[i-1][j]*(cnt[j]-(i-1))%P)%=P;}return f[N*M][bin[top]-1]; } inline void DFS(int dep,int x,int y) {if (y==M+1) {DFS(dep,x+1,1); return;}if (x==N+1) {(ANS+=(LL)DP()*(dep&1? -1:1)%P)%=P; return;}DFS(dep,x,y+1);bool flag=1;for (int i=0; i<=8 && flag; i++)if (mp[x+dx[i]][y+dy[i]]=='X') flag=0;if (flag) mp[x][y]='X',DFS(dep+1,x,y+1),mp[x][y]='.'; } int main() {bin[0]=1; for (int i=1; i<=10; i++) bin[i]=bin[i-1]<<1;scanf("%d%d",&N,&M);for (int i=1; i<=N; i++) scanf("%s",mp[i]+1);DFS(0,1,1);printf("%d\n",(ANS+P)%P);return 0; }

菜雞.jpg

轉載于:https://www.cnblogs.com/DaD3zZ-Beyonder/p/5957956.html

總結

以上是生活随笔為你收集整理的【BZOJ-2669】局部极小值 状压DP + 容斥原理的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。