2010-02-07.sgu502狀態(tài)壓縮dp <推薦題目>
sgu502:狀態(tài)壓縮dp
首先要知道這樣一個(gè)事實(shí)
如果有5個(gè)數(shù)，要填充到如下x的位置上
*xx*x*x**x
那么只要這5個(gè)數(shù)產(chǎn)生的部分模的結(jié)果:
(x + x * 10^3 + x * 10^5 + x * 10^7 + x * 10^8) % 17
的結(jié)果相同，那么這5個(gè)數(shù)能產(chǎn)生這個(gè)相同結(jié)果的所有排列都是等價(jià)的。
這和使用狀態(tài)壓縮進(jìn)行優(yōu)化的哈密頓路徑的搜索方法是一樣的(想要詳細(xì)的了解這個(gè)問題可以參考
MasterLuo的文章，我覺的寫的很好， http://www.shnenglu.com/EyeOfProvidence/archive/2010/01/10/105356.html
pku2288就是關(guān)于這個(gè)問題的一個(gè)應(yīng)用)
如下的dfs中，
stat表示所有可用位的使用狀態(tài)
mod表示前step個(gè)數(shù)產(chǎn)生的部分模。
step表示為第step個(gè)數(shù)。
對于剛才說的事實(shí)，如果前step個(gè)數(shù)填充的狀態(tài)是相同的，那么所有模相等的狀態(tài)就可以合并
也就是將前step個(gè)數(shù)的占用同樣的step個(gè)位能產(chǎn)生的 P(step,step)個(gè)狀態(tài)，減少到17個(gè)
?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?}