题意
n个问题，解决的顺序影响正确的概率，无论之前解决的问题是否答对，当前问题 j 答对概率为max{a[i][j]} (i为解决过的问题)。求答对题目的最大期望和对应的答题顺序。T组测试，T (0 < T ≤ 100)， n (0 < n ≤ 10)。
分析
n那么小，就想到状态压缩DP（我不会dfs做这题）
假设当前状态是 i ， i 对应的01串的1代表已经解决的问题，0代表尚未解决的，那么它肯定是由某个已解决的问题还没解决的状态转移过来的，也就是由其中一个1变为0的状态。所以我们枚举它里面的每个1，i&(1<<l) ==1 表示第l个数字是1， j = i-(1<<l) 得到 j 状态。
dp表示状态i的期望，dp[i]=dp[j] max(a[i][j]) 。因为多答出一题，期望就增加（1*答出这题的概率）。
同时每个状态用d储存答题顺序（期望最大且字典序最小的答题顺序）。
这句判断字典序：ex==dp[i] && d[i]>=d[i-(1<<l)] //如果新的dp[i-(1<<l)]的字典序比较小，dp[i]更新。因为一开始d都是0，所以要用≥，不然第一个样例就不会输出A。
注意如果计算的时候用浮点数，比较大小还要设置个精度。也可以直接储存整数，最后除以100化为 小数。
代码
代码语言：javascript复制#include<cstdio>
#include<cstring>
#include<iostream>
using namespace std;
int t,n;
int a[15][15];
int dp[1050];
string d[1050];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=0; i<n; i )
for(int j=0; j<n; j )
scanf("%d",&a[i][j]);
d[0]="";
memset(dp,0,sizeof(dp));
for(int i=1; i<(1<<n); i )
for(int l=0; l<n; l )
if (i&(1<<l))// solve l
{
int ex=0;
for(int u=0; u<n; u )
{
if(i&(1<<u) && a[u][l]>ex)//u have been solved
{
ex=a[u][l];
}
}
ex =dp[i-(1<<l)];
char now='A' l;//第l个问题的字母表示
if(ex>dp[i] || ex==dp[i] && d[i]>=d[i-(1<<l)])
{
d[i]=d[i-(1<<l)] now;
dp[i]=ex;
}
}
double ans=dp[(1<<n) - 1]*1.0/100;
printf("%.2lfn",ans);
cout<<d[(1<<n) - 1]<<endl;
}
return 0;
}
