2010-02-07.sgu502狀態壓縮dp <推薦題目>
sgu502:狀態壓縮dp
首先要知道這樣一個事實
如果有5個數，要填充到如下x的位置上
*xx*x*x**x
那么只要這5個數產生的部分模的結果:
(x + x * 10^3 + x * 10^5 + x * 10^7 + x * 10^8) % 17
的結果相同，那么這5個數能產生這個相同結果的所有排列都是等價的。
這和使用狀態壓縮進行優化的哈密頓路徑的搜索方法是一樣的(想要詳細的了解這個問題可以參考
MasterLuo的文章，我覺的寫的很好， http://www.shnenglu.com/EyeOfProvidence/archive/2010/01/10/105356.html
pku2288就是關于這個問題的一個應用)
如下的dfs中，
stat表示所有可用位的使用狀態
mod表示前step個數產生的部分模。
step表示為第step個數。
對于剛才說的事實，如果前step個數填充的狀態是相同的，那么所有模相等的狀態就可以合并
也就是將前step個數的占用同樣的step個位能產生的 P(step,step)個狀態，減少到17個
?1?
?2?#define?bin(x)?(1?<<?(x))
?3?const?int?N?=?20;
?4?char?s[N];
?5?int?num[N],len,out[N],ten[N],val[N];
?6?bool?vis[bin(19)][19];
?7?
?8?bool?dfs(int?stat,int?mod,int?step)
?9?{
10???if?(vis[stat][mod])?{?return?false;?}
11???vis[stat][mod]?=?true;
12?
13???if?(step?==?len)?{?return?mod?==?0;?}
14???for?(int?i?=?0;i?<?len;?i++)?{
15???????if?(stat?&?bin(i))?{?continue;?}
16???????if?(num[step]?==?0?&&?i?==?len-1)?{?continue;?}?//第一位不能為0
17???????out[i]?=?num[step];
18???????if?(dfs(stat?|?bin(i),(mod?+?num[step]?*?val[i])%17,step?+?1))?{
19???????????return?true;
20???????}
21???}
22???return?false;
23?}
24?//http://www.shnenglu.com/schindlerlee
25?int?main()
26?{
27???int?i,j,k;
28???scanf("%s",s);
29???len?=?strlen(s);
30???val[0]?=?1;
31???for?(i?=?1;i?<?len;i++)?{?val[i]?=?(val[i-1]?*?10)?%?17;?}
32???for?(i?=?0;i?<?len;i++)?{?num[i]?=?s[i]?-?'0';?}
33???if(dfs(0,0,0))?{
34???????for?(i?=?len?-?1;i?>=?0;i--)?{
35???????????printf("%d",out[i]);
36???????}
37???????printf("\n");
38???}else?{
39???????printf("-1\n");
40???}
41?
42???return?0;
43?}