状态压缩dp（hdu2167）

 1 #include <stdio.h>
 2 #include <string.h>
 3 #include <iostream>
 4 #include <sstream>
 5 using namespace std;
 6 int matrix[15][15];
 7 int dp[1<<15][15],situation[1600],bit[15],head[1000000],e;
 8 struct node
 9 {
10     int v,next;
11 }g[1000000];;
12 int max(const int &a, const int &b)
13 {
14     return a < b ? b : a;
15 }
16 
17 void addEdge(int u, int v)
18 {
19     g[e].v = v;
20     g[e].next = head[u];
21     head[u] = e++;
22 }
23 int count(int i, int ss, int n)//计算状体第i行的状态s所取的数的和
24 {
25     int ret = 0;
26     int j = 0;
27     for(j=0; j<n; ++j)
28     {
29         if(bit[j] & ss)
30             ret += matrix[i][j];
31     }
32     return ret;
33 }
34 bool check(int s, int ss,int n)//检查s和ss是否可容
35 {
36     
37     if(s&ss) return false;
38     if((s<<1)&ss) return false;
39     if((s>>1)&ss) return false;
40     return true;
41 }
42 int main()
43 {
44     int n,i,j,m,s,ss;
45     char str[100];
46     bit[i=0] = 1;
47     for(i=1; i<15; ++i)
48         bit[i] = bit[i-1]<<1;
49     m = 1<<15;
50     for(i=0,j=0; i<m; ++i)
51         if(!(i&(i<<1)))//求出有效的状态
52             situation[j++]= i;
53     while(gets(str))
54     {
55         memset(dp,0,sizeof(dp));
56         e = 0;
57         memset(head,-1,sizeof(head));
58         n = 0;
59         do
60         {
61             j = 0;
62             stringstream scin(str);
63             while(scin>>matrix[n][j]) j++;
64             n++;
65             gets(str);
66             if(str[0]==‘\0‘) break;
67 
68         }while(true);
69         m = 1<<n;
70         for(i=0;situation[i]<m; ++i)//判断哪两个状体相容，然后用邻接表存储
71             for(j=0; situation[j]<m; ++j)
72                 if(check(situation[i],situation[j],n))
73                     addEdge(i,j);
74         for(i=0; situation[i]<m; ++i)
75             dp[situation[i]][0] = count(0,situation[i],n);
76         for(i=1; i<n; ++i)
77             for(s=0;situation[s]<m; ++s)
78             {
79                 for(j=head[s];j!=-1;j=g[j].next)
80                 {
81                     dp[situation[g[j].v]][i] = max(dp[situation[g[j].v]][i],dp[situation[s]][i-1]+count(i,situation[g[j].v],n));
82                 }
83             }
84         int ans = 0;
85         for(i=0; situation[i]<m; ++i)
86         {
87             ans = max(ans,dp[situation[i]][n-1]);
88         }
89         printf("%d\n",ans);
90     }
91     return 0;
92 }