链接：http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3502
1 #include <iostream> 2 #include <cstdio> 3 #include <string> 4 #include <cmath> 5 #include <cstring> 6 using namespace std; 7 int T, N; 8 double p[15][15], dp[1<<15]; 9 string s[1<<15]; 10 const double eps=1e-8; 11 int Sign( double x ) 12 { 13 if( fabs(x)<eps )return 0; 14 return x>0?1:-1; 15 } 16 int main( ) 17 { 18 scanf("%d", &T); 19 while(T--){ 20 scanf("%d",&N ); 21 for(int i=0; i<N; ++ i){ 22 for( int j=0; j<N; ++j ){ 23 scanf("%lf", &p[i][j]); 24 } 25 } 26 int t=1<<N;double q; 27 28 memset(dp, 0, sizeof dp); 29 if(N==1)s[1]="A"; // N=1 p=0 不能被更新到~ 30 for(int i=1; i<t; ++ i){ 31 for( int j=0; j<N; ++ j ){// 更新到当前位 32 if( i&(1<<j)) { 33 q=0; 34 for( int k=0; k<N; ++ k ){ // 已经被更新过的 35 if(i&(1<<k)) 36 q=max(q, p[k][j]); 37 } 38 } 39 q=dp[i^(1<<j)]+q/100.0; 40 if( Sign(q-dp[i])>0 || Sign(q-dp[i])==0 && s[i^(1<<j)]<s[i]){ 41 dp[i]=q; 42 s[i]=s[i^(1<<j)]; 43 s[i]+=('A'+j); 44 } 45 } 46 } 47 48 printf("%.2f %s ", dp[t-1], s[t-1].c_str()); 49 } 50 return 0; 51 }