UESTC_The Most Wonderful Competition CDOJ 56

The Most Wonderful Competition

Time Limit: 3000/1000MS (Java/Others) Memory Limit: 65535/65535KB (Java/Others)

Last week, School of Applied Mathematics held a competition of flying kite, contestants are divided into pairs, and one contestant competes with another in each pair. As we know, different way dividing pairs may bring different splendid level value, which appears as a real numbers. Now Miss Ye wants to know how to divide the competitor in order to attain maximum splendid level.

Input

The first line of the input contains one integer

For each test case, in the first line there is an integer

In the next

Output

For each case, output the maximum total splendid level value accurate to two digits after the radix point.

Sample input and output

Sample Input	Sample Output
1 2 0.0 1.0 1.0 0.0	1

Source

电子科技大学第七届ACM程序设计大赛初赛

解题报告

简单集合DP，f(i)表示选择这i个元素时的最高加成

 1 #include <iostream>
 2 #include <algorithm>
 3 #include <cstring>
 4 #include <cstdio>
 5 
 6 using namespace std;
 7 const int maxn = 16 + 15;
 8 double value[maxn][maxn];
 9 double f[1 << 16];
10 bool   arrive[1<<16];
11 int n;
12 double ans;
13 
14 
15 double dfs(int cur,int val)
16 {
17   if (arrive[val])
18    return f[val];
19   arrive[val] = true;
20   double &ans = f[val] = -1e100;
21   if (val)
22    {
23          for(int i = 0 ; i < n ; ++ i)
24           if (val >> i & 1 && i != cur)
25            {
26               int next = 1;
27               int newval = val;
28               newval &= ~(1 << i);
29               newval &= ~(1 << cur);
30               for(int j = 0 ; j < n ; ++ j)
31                if (newval >> j & 1)
32                 {
33                     next = j;
34                     break;
35                 }
36               ans = max(ans,dfs(next,newval) + value[cur][i] );
37            }
38    }
39   else
40    ans = 0;
41   return ans;
42 }
43 
44 int main(int argc,char *argv[])
45 {
46   int Case;
47   scanf("%d",&Case);
48   while(Case--)
49    {
50          memset(arrive,false,sizeof(arrive));
51          scanf("%d",&n);
52          for(int i = 0 ; i < n ; ++ i)
53           for(int j = 0 ; j < n ; ++ j)
54            scanf("%lf",&value[i][j]);
55          dfs(0,(1<<n)-1);
56          printf("%.2lf
",f[(1<<n)-1]);
57    }
58   return 0;
59 }

No Pain , No Gain.