HDU4624 Endless Spin 【最大最小反演】【期望DP】

题目分析：

题目是求$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出一种简便方法。

代码：

 #include<bits/stdc++.h>

 using namespace std;

 const int maxn = ;

 int n;

 long long f[maxn][maxn*maxn][];

 int C(int now){return (now+)*now/;}

 struct nb{

     long long zs;

     long long xs[];

 }ans;

 void cunt(long long alpha,long long beta){

     ans.zs += alpha/beta;alpha %= beta;

     for(int i=;i<=;i++){

     alpha*=;

     ans.xs[i] += alpha/beta; alpha%=beta;

     }

 }

 void work(){

     f[][][] = ;

     for(int i=;i<=n;i++){

     for(int j=;j<=C(i);j++){

         for(int k=i-;k>=;k--){

         if(C(i-k-) > j) break;

         f[i][j][] += f[k][j-C(i-k-)][];

         f[i][j][] += f[k][j-C(i-k-)][];

         }

     }

     }

     for(int i=;i<=;i++) ans.xs[i] = ;

     ans.zs = ;

     for(int i=;i<=n;i++){

     for(int j=;j<C(i);j++){

         cunt(C(n)*(f[i][j][]-f[i][j][]),(C(n)-j-C(n-i)));

     }

     }

     /*double exm = 5.123456789;

     printf("%.0lf\n",exm);

     printf("%.1lf\n",exm);

     printf("%.2lf\n",exm);

     printf("%.3lf\n",exm);

     printf("%.4lf\n",exm);

     printf("%.5lf\n",exm);

     printf("%.6lf\n",exm);

     printf("%.7lf\n",exm);

     printf("%.8lf\n",exm);

     exit(0);*/

     for(int i=;i>=;i--){

         if(i ==  && ans.xs[]>=)ans.xs[i]++;

         long long p = ans.xs[i]/;

         ans.xs[i] -= p*; if(ans.xs[i] < ) p--,ans.xs[i]+=;

         ans.xs[i-] += p;

     }

     ans.zs += ans.xs[];

     printf("%lld.",ans.zs);

     for(int i=;i<=;i++) printf("%lld",ans.xs[i]);

     printf("\n");

 }

 int main(){

     int T; scanf("%d",&T);

     while(T--){

     scanf("%d",&n);

     memset(f,,sizeof(f));

     work();

     }

     return ;

 }