hdu 1565

 1 #include<iostream>
 2 #include<stdio.h>
 3 #include<cstring>
 4 #include<cstdlib>
 5 #include<queue>
 6 #include<math.h>
 7 #include<algorithm>
 8 
 9 #define maxx 1<<21
10 using namespace std;
11 
12 int mat[22][22],n,dp[22][60002],valid[60002];
13 
14 int sum(int p,int k,int n) // 第p层  状态k   共n层
15 {
16     int m=1<<n;
17     int ans=0;
18     for(int i=0; i<n; i++)
19         if(k&(1<<i))//{printf("1<<i  %d %d 
",i,1<<i);
20             ans+=mat[p][n-i-1];//}
21     return ans;
22 }
23 
24 void getnum()
25 {
26     int num=0;
27     for(int i=0; i<maxx; i++)
28         if((i&(i<<1))==0)
29             valid[num++]=i;
30 }
31 
32 int solve()
33 {
34     int final1=0;
35     int m=(1<<n);
36     memset(dp,-1,sizeof(dp));//  前i层   且i层状态为 j  获得的 最大的
37     for(int i=0; valid[i]<m; i++)
38     {
39         dp[0][valid[i]]=sum(0,valid[i],n);
40         //printf("temp   %d %d  %d
",valid[i],sum(0,valid[i],n),dp[0][valid[i]]);
41     }
42 
43     for(int i=1; i<n; i++)
44     {
45         for(int j=0; valid[j]<m; j++) //状态 valid[j]
46         {
47             for(int k=0; valid[k]<m; k++)
48             {
49                 if(dp[i-1][valid[k]]!=-1&&(valid[j]&valid[k])==0)
50                 {
51                     if(dp[i][valid[j]]==-1)
52                         dp[i][valid[j]]=dp[i-1][valid[k]]+sum(i,valid[j],n);
53                     else
54                         dp[i][valid[j]]=max(dp[i][valid[j]],dp[i-1][valid[k]]+sum(i,valid[j],n));
55 
56                 }
57             }
58         }
59     }
60 
61     for(int i=0; valid[i]<m; i++)
62     {
63         if(final1<dp[n-1][valid[i]])
64             final1=dp[n-1][valid[i]];
65     }
66 
67 
68     return final1;
69 }
70 
71 int main()
72 {
73     getnum();
74     while(~scanf("%d",&n))
75     {
76         for(int i=0; i<n; i++)
77             for(int j=0; j<n; j++)
78                 scanf("%d",&mat[i][j]);
79         if(n==0)
80             printf("0
");
81         else
82             printf("%d
",solve());
83 
84     }
85     return 0;
86 }