题目分析：
题目是求$E(MAX_{i=1}^n(ai))$, 它等于$E(sum_{s subset S}{(-1)^{|s|-1}*min(s))} = sum_{s subset S}{(-1)^{|s|-1}*E(min(s))}$。
那么设计期望DP，令$f[i][j][k]$表示前i个球，可选的区间为j个，球的个数是奇数还是偶数。然后就是要写一个高精度，不一定要真的写，可以yy出一种简便方法。
代码：
1 #include<bits/stdc++.h> 2 using namespace std; 3 4 const int maxn = 55; 5 6 int n; 7 8 long long f[maxn][maxn*maxn][2]; 9 10 int C(int now){return (now+1)*now/2;} 11 12 struct nb{ 13 long long zs; 14 long long xs[160]; 15 }ans; 16 17 void cunt(long long alpha,long long beta){ 18 ans.zs += alpha/beta;alpha %= beta; 19 for(int i=1;i<=150;i++){ 20 alpha*=10; 21 ans.xs[i] += alpha/beta; alpha%=beta; 22 } 23 } 24 25 void work(){ 26 f[0][0][0] = 1; 27 for(int i=1;i<=n;i++){ 28 for(int j=0;j<=C(i);j++){ 29 for(int k=i-1;k>=0;k--){ 30 if(C(i-k-1) > j) break; 31 f[i][j][0] += f[k][j-C(i-k-1)][1]; 32 f[i][j][1] += f[k][j-C(i-k-1)][0]; 33 } 34 } 35 } 36 for(int i=0;i<=150;i++) ans.xs[i] = 0; 37 ans.zs = 0; 38 for(int i=1;i<=n;i++){ 39 for(int j=0;j<C(i);j++){ 40 cunt(C(n)*(f[i][j][1]-f[i][j][0]),(C(n)-j-C(n-i))); 41 } 42 } 43 /*double exm = 5.123456789; 44 printf("%.0lf ",exm); 45 printf("%.1lf ",exm); 46 printf("%.2lf ",exm); 47 printf("%.3lf ",exm); 48 printf("%.4lf ",exm); 49 printf("%.5lf ",exm); 50 printf("%.6lf ",exm); 51 printf("%.7lf ",exm); 52 printf("%.8lf ",exm); 53 exit(0);*/ 54 for(int i=150;i>=1;i--){ 55 if(i == 15 && ans.xs[16]>=5)ans.xs[i]++; 56 long long p = ans.xs[i]/10; 57 ans.xs[i] -= p*10; if(ans.xs[i] < 0) p--,ans.xs[i]+=10; 58 ans.xs[i-1] += p; 59 } 60 ans.zs += ans.xs[0]; 61 printf("%lld.",ans.zs); 62 for(int i=1;i<=15;i++) printf("%lld",ans.xs[i]); 63 printf(" "); 64 } 65 66 int main(){ 67 int T; scanf("%d",&T); 68 while(T--){ 69 scanf("%d",&n); 70 memset(f,0,sizeof(f)); 71 work(); 72 } 73 return 0; 74 }