<span>模拟101 题解</span>

简单模拟。

注意获胜条件有四种情况不是三种

对于每个点封掉$d$条路。

考虑反向$dijkstra$跑最短路。

对于每个元素$i$，当第$d+1$次取出时视作$dis(i,n)$，更新相邻的点。

考场上的思路是，求出一个数组表示$i$步之后形成一个极大连续的用掉的气的区间$[l,r]$的概率。

根据这个数组，可以直接概率乘当前步的贡献统计答案，然而问题似乎并没有那么简单。

所以颓了$std$，顺便压了压行，其中英文的部分是原有的注释。

大致思路是类似的，仍然要考虑每个连续的区间。

一些理解在$std$的中文注释。

 1 #include<algorithm>
 2 #include<cstdio>
 3 #include<iostream>
 4 #include<vector>
 5 using namespace std;
 6 const int N=205;
 7 long double C[N][N];// binomial coefficient
 8 struct Stat{ // contains stats about a random variable
 9     double sum_,cnt_;
10     Stat():sum_(0),cnt_(0){}
11     double E(){
12         if(cnt_==0) return 0;    
13         return sum_/cnt_;
14     }
15     void AddInfo(double expected,double cnt){
16         sum_+=expected*cnt;
17         cnt_+=cnt;
18     }
19 }w[N][N],dp[N][N];
20 int n,g,t;
21 long double cap_avg(int x,int y,int upper){
22     if(upper>n) return 0;
23     return (x+y+1.0)/2;
24 }
25 int main(){
26     cin>>n>>g>>t;
27     vector<int> c(n+1);
28     for(int i=1;i<=n;++i) cin>>c[i],c[i]=min(c[i],g); // tables larger than g don't make sense
29     sort(c.begin()+1,c.end());
30     c.resize(t+n+1,g); // add virtual tables that catch overflow
31     int m=c.size();
32     for(int i=0;i<=t;++i) for(int j=C[i][0]=1;j<=i;++j) C[i][j]=C[i-1][j]+C[i-1][j-1];
33     //w[i][j] has the statistics of filling up interval [i, j) with customers conditioned upon
34     //*no one else* coming to the restaurant. Tables are numbered from 0 in ascending order.
35     for(int i=m-1;~i;--i){
36         w[i][i].AddInfo(0,1); // empty interval can be occupied in only one way
37         for(int j=i+1;j<m;++j) if(i+t>=j){ // only process intervals of length <= t
38             for(int k=i;k<j;++k){
39                 //merge [i,k) and [k+1,j) by occupying table k 
40                 long double cnt=w[i][k].cnt_*w[k+1][j].cnt_*(c[k+1]-c[i])*C[j-i-1][k-i];//j-i为区间长度 其中规定第k个最后一个出现 以保证不重 在前j-i-1个精中选择k-i个给左半边气，其余的直接分给右半边
41                 long double expected=w[i][k].E()+w[k+1][j].E()+cap_avg(c[k+1],c[i],k+1);
42                 w[i][j].AddInfo(expected,cnt);
43             }
44         }
45     }
46     //dp[i][k] has the statistics of filling up the first i tables with k different groups,
47     //conditioned upon no one else coming. Some of the first i tables might be empty.
48     for(int i=0;i<m;++i){//已经处理完的气
49         if(i<=t) dp[i][i]=w[0][i];
50         for(int k=0;k<=t;++k) if(dp[i][k].cnt_>0) for(int j=i+1;j<m;++j){//k为当前轮用了多少精 j为转移到多少气
51             int new_cnt=k+((j-1)-i); //因为第j个不能用 第i个也不能用 所以(j-1)-i为当前一段连续区间中用到了多少个气 也就是精的增加量
52     　　　　 //所以newcnt为之后处理了多少个精
53             if(new_cnt>t) break;
54             long double expected=dp[i][k].E()+w[i+1][j].E();//用了[i+1,j)的气
55             long double cnt=dp[i][k].cnt_*w[i+1][j].cnt_*C[new_cnt][k];
56             dp[j][new_cnt].AddInfo(expected,cnt);
57             //dp[i][j] 考虑区间[0,i] 其中用到的气分成若干段
58             //第i个气一定没有被用   j是已经考虑完了j个精
59         }
60     }
61     printf("%.12lf\n",dp[m-1][t].E());
62     return 0;
63 }