SRM 656 Div1 Easy RandomPancakeStack
dp(i,j):i番目の操作でj番目のパンケーキを置く確率
class RandomPancakeStack { public: int N; double memo[300][300]; double dp(int i,int j){ if(memo[i][j]>1e-9) return memo[i][j]; if(i==0) return memo[i][j]=1.0/N; double res=0; for(int k=j+1;k<N;k++) res+=dp(i-1,k)/(N-i); return memo[i][j]=res; } double expectedDeliciousness(vector <int> d) { N=d.size(); REP(i,300)REP(j,300) memo[i][j]=0; double res=0; REP(i,N)REP(j,N) res+=dp(i,j)*d[j]; return res; }