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.cppblog.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.cppblog.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 }