題目描述：
求12×12矩陣上的互不嵌套的k個哈密頓回路的方案數。
http://acm.hdu.edu.cn/showproblem.php?pid=4285算法分析：
求哈密頓路方案數不用多說了，相信大家都會插頭DP。
之前在clarification里面看到有同學說暴空間，相信他一定沒刷過sgu 1519...
離散化解決空間問題，我用的是map。四進制表示狀態。
求k個哈密頓回路就多加一維狀態，表示目前已經有了多少組哈密頓回路。
至于互不嵌套嘛。。。。 好吧，我承認這不是我自己想出來的。。。。 就是在左右括號相遇的時候判斷有多少組括號包含了這組括號。
如果是奇數的話，就跳過這個狀態。
證明如下：
在外面的括號想要合并，且不包含到當前括號，必須一次合并偶數個。
如果外面有偶數個括號，其實后面未必合法，但是非法的時候一定是奇數個。因為合法的合并都是一次性合并偶數個。。。。
說的有點亂。。。。然后是trick
比如1 2 2 0 **\n**這組應該是1。。。 好犀利。。。。。
tianjin2012-online H
1 #include<iostream>
2 #include<cstdio>
3 #include<map>
4 #include<cassert>
5 using namespace std;
6 const int MAXN = 42000;
7 const int mod = (int)1e9+7;
8 int dp[2][37][MAXN];
9 int bound[20], n, m, k, hash[MAXN], len;
10 char ch[20][20];
11 map<int, int> MP;
12 int num[20];
13 // debug
14 void OP(){
15 for(int i = 0; i < len; i++)
16 cout<< num[i] <<" "; cout<< endl;
17 }
18 // work
19 inline void make(int mask) {
20 for(int i = 0; i < len; i++, mask >>= 2 )
21 num[i] = mask & 3;
22 }
23 inline int make(){
24 int ans = 0;
25 for(int i =len-1; i >=0; i--){
26 ans <<= 2;
27 ans |= num[i];
28 }
29 return ans;
30 }
31 inline void process(int s,int p,int q,int pos,char c){
32 int val = dp[s][q][p];
33 int &a = num[pos], &b = num[pos + 1];
34 int mask, nq = q;
35 // cout<<"mask: "<<q <<" "<<c<<" "<<val<<endl;OP();
36 if( c == '*') {
37 if(a || b) return ;
38 }
39 else {
40 if(a && b ) {
41 if(a != b) {
42 if(a == 1){
43 nq ++;
44 int tmp = 0;
45 for(int p = pos- 1; p >=0; p-- )
46 tmp += (num[p] == 1) - (num[p] == 2);
47 if(tmp&1) return ;
48 }
49 a = b = 0;
50 }
51 else if(a == 1){
52 int tmp = 1,p;
53 a = b= 0;
54 for( p = pos + 2; p < len; p++){
55 tmp += (num[p] == 1) - (num[p] == 2);
56 if(tmp == 0) break;
57 }
58 // assert(tmp == 0);
59 num[p] = 1;
60 }
61 else {
62 int tmp = 0, p = -1;
63 for(p = pos ; p>=0 ; p--){
64 tmp += (num[p] == 1) - (num[p] == 2);
65 if(tmp == 0) break;
66 }
67 a = b = 0;
68 assert(tmp == 0);
69 num[p] = 2;
70 }
71 }
72 else if(a || b) {
73 int v = a ? a : b;
74 a = b = 0;
75 a = v;
76 int msk = make();
77 // cout<<"new: "<<nq<<endl;OP();
78 if(pos == m-1) msk <<= 2;
79 msk = MP[msk];
80 dp[s^1][nq][msk] += val;
81 dp[s^1][nq][msk] %= mod;
82 a = 0, b = v;
83 }
84 else {
85 a = 1, b = 2;
86 }
87 }
88 //cout<<"new: "<<nq<<" "<<endl;OP();
89 if(nq > k) return ;
90 mask = make();
91 if(pos == m-1 ) {
92 if(num[pos+1]) return ;
93 mask <<= 2;
94 }
95 mask = MP[mask];
96 dp[s^1][nq][mask] += val;
97 dp[s^1][nq][mask] %= mod;
98
99 }
100 // init
101 int now =0, top = 0;
102 void prec(int lvl,int mask, int tmp){
103 if(tmp > 0) return ;
104 if(lvl == top ) {
105 if(tmp) return ;
106 ++ now;
107 MP[mask] = now ;
108 hash[now] = mask;
109 }
110 else {
111 prec(lvl + 1, mask << 2 | 2, tmp-1);
112 prec(lvl + 1, mask << 2 | 1, tmp+1);
113 if(lvl > 0)
114 prec(lvl + 1, mask << 2, tmp);
115 }
116 }
117 // main
118 int main(){
119 MP[0] =(hash[0] = 0);
120 for(top = 1; top <= 13; top ++) {
121 prec(0, 0, 0);
122 bound[top] = now;
123 }
124 int cas; cin >> cas;
125 while(cas --) {
126 // io
127 scanf("%d%d%d",&n,&m,&k);
128 for(int i =0 ; i < n; i++)
129 scanf("%s",ch[i]);
130 // error handle
131 if(k > 36) {
132 puts("0"); continue;
133 }
134 // process
135 len = m+1;
136 for(int i = 0; i <= bound[len]; i++)
137 for(int j = 0; j <= k; j++)
138 dp[0][j][i] = 0;
139 dp[0][0][0] = 1;
140 int s = 0;
141 for(int i = 0; i < n; i++)
142 for(int j = 0; j < m; j++,s ^= 1) {
143 for(int p = 0; p <= bound[len]; p++)
144 for(int q =0; q <= k; q++) dp[s^1][q][p] = 0;
145 for(int p = 0; p <= bound[len]; p++)
146 for(int q = 0; q <= k ; q++){
147 if(dp[s][q][p]) {
148 // cout<<"pos: "<<i<<" "<<j<<endl;
149 make(hash[p]);
150 process(s, p, q, j, ch[i][j]);
151 }}}
152 printf("%d\n",(int) dp[s][k][0]);
153 }
154 }
155 posted on 2012-09-10 21:09
西月弦 閱讀(1161)
評論(5) 編輯 收藏 引用 所屬分類:
解題報告