sdut1283Five in a Row, Again

 1 #include <iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 #include<stdlib.h>
 6 #include<vector>
 7 using namespace std;
 8 int dp[15][5010],o[15][5010];
 9 int w[15][15],ee[15][15],s[15];
10 int main()
11 {
12     int i,j,n,t,e;
13     cin>>t;
14     while(t--)
15     {
16         memset(dp,0,sizeof(dp));
17         memset(o,0,sizeof(o));
18         cin>>n;
19         for(i = 1; i <= n ;i++)
20             for(j = 1; j <= n ; j++)
21             cin>>w[i][j];
22         for(i = 1; i <= n ; i++)
23             for(j = 1; j <= n ;j++)
24             cin>>ee[i][j];
25         for(i = 1; i <= n ;i++)
26             cin>>s[i];
27         if(n==1)
28         {
29             cout<<"0\n";
30             continue;
31         }
32         for(i = 1 ; i < n ;i++)
33         {
34             if(s[1]>s[i+1])
35             {
36                 dp[1][1<<(i-1)] = ee[1][i+1];
37             }
38             else
39             dp[1][1<<(i-1)] = 0;
40             o[1][1<<(i-1)] = 1;
41         }
42         for(i = 2; i < n ;i++)
43         {
44             for(j = 0 ; j < (1<<(n-1)) ; j++)
45             {
46                 int ts=s[1];
47                 if(!o[i-1][j]) continue;
48                 for(e = 1 ; e < n ; e++)
49                 {
50                     if(j&(1<<(e-1)))
51                     {
52                         ts+=w[1][e+1];
53                     }
54                 }
55                 for(e = 1; e < n ; e++)
56                 {
57                     if((j&(1<<(e-1)))==0)
58                     {
59                         if(ts>s[e+1])
60                         dp[i][j+(1<<(e-1))] = max(dp[i][j+(1<<(e-1))],dp[i-1][j]+ee[1][e+1]);
61                         else
62                         dp[i][j+(1<<(e-1))] = max(dp[i][j+(1<<(e-1))],dp[i-1][j]);
63                         o[i][j+(1<<(e-1))] = 1;
64                     }
65                 }
66             }
67         }
68         cout<<dp[n-1][(1<<(n-1))-1]<<endl;
69     }
70     return 0;
71 }
72  
73 
74 
75 
76 /**************************************
77     Problem id    : SDUT OJ 1283 
78     User name    : shang 
79     Result        : Accepted 
80     Take Memory    : 1060K 
81     Take Time    : 0MS 
82     Submit Time    : 2014-02-14 23:02:39  
83 **************************************/