【题意】：略

【题解】：最多只有10道题目，很容易想到状态压缩，对于每种状态枚举当前在尝试哪道题目，然后期望的转移比较容易。
               注意本题会卡精度，还要输出最小的字典序方案。
               复杂度是O(2^n*n*n)，用string记录方案很方便。

【代码】：
 1 #include "iostream"
 2 #include "cstdio"
 3 #include "cstring"
 4 #include "algorithm"
 5 #include "vector"
 6 #include "queue"
 7 #include "cmath"
 8 #include "string"
 9 #include "cctype"
10 #include "map"
11 #include "iomanip"
12 #include "set"
13 #include "utility"
14 using namespace std;
15 typedef pair<int, int> pii;
16 #define pb push_back
17 #define mp make_pair
18 #define fi first
19 #define se second
20 #define sof(x) sizeof(x)
21 #define lc(x) (x << 1)
22 #define rc(x) (x << 1 | 1)
23 #define lowbit(x) (x & (-x))
24 #define ll long long
25 #define eps 1e-10
26 int n;
27 double p[11][11];
28 double dp[1<<11];
29 string s[1<<11];
30 
31 void solve() {
32     int nn = 1 << n;
33     dp[0] = 0.0;
34     s[0] = "";
35     for(int i = 1; i < nn; i++) {
36         dp[i] = -1.0;
37         for(int j = 0; j < n; j++) {
38             if(i & (1 << j)) {
39                 double pp = 0.0;
40                 for(int k = 0; k < n; k++) {
41                     if(i & (1 << k)) pp = max(pp, p[k][j]);
42                 }
43                 int m = i - (1 << j);
44                 double tmp = dp[m] + pp;
45                 if(dp[i] + eps < tmp || (dp[i] - eps < tmp && s[i] > s[m])) {//watashi判精度的方法，妙~
46                     dp[i] = tmp;
47                     char ch = j + 'A';
48                     s[i] = s[m] + ch;
49                 }
50             }
51         }
52     }
53     printf("%.2f\n", dp[nn-1]);
54     cout << s[nn-1] << endl;
55 }
56 
57 int main() {
58     int T;
59     cin >> T;
60     while(T--) {
61         cin >> n;
62         for(int i = 0; i < n; i++) {
63             for(int j = 0; j < n; j++) {
64                 cin >> p[i][j];
65                 p[i][j] /= 100.0;
66             }
67         }
68         solve();
69     }
70     return 0;
71 }
72