D. Deceptive Dice(數學期望(平均值))

這道題還是按照題解來說比較好了解：

主要是因為題目說的兩個人都是最優政策，是以我們比較他們的平均值，因為都是最優，是以每次他們的期望值都一樣，是以需要比k輪，直到這個遊戲結束；上面的例子n=20，k=3；對于第一輪那麼期望值為10.5，那麼要進行第二輪那麼就必須第一輪是搖到的分數小于10.5（機率為10/20），是以在第二輪裡面，那麼期望就是：

按照這樣思路一直推下去，就出來答案了；

這道題主要是難點就在與這個遞推規律；

AC代碼：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
double sum[110];
ll n,k;
int main(){
	scanf("%lld %lld",&n,&k);
	for(ll i=1;i<=n;i++){
        sum[i]=sum[i-1]+i;
	}
	  double t=sum[n]/n;
   for(ll i=2;i<=k;i++){
   	   ll  next=ll(t);//求下一次沒有達到上一次期望值(平均值)的機率的分子
   	   //cout<<sum[n]-sum[next]<<endl;
   	    t=(sum[n]-sum[next])/n+(next)*t/n;
   }
   printf("%.8lf\n",t);//因為題目要求e-7是以直接cout會wa掉
	return 0;
}