概率期望

洛谷1850 - 换教室

• https://www.luogu.com.cn/problem/P1850
• 难度：蓝

题意

• 有 $nn$ 节课。学生需要按顺序依次完成所有的 $nn$ 节课。
• 若不提交申请，时刻 $ii$ 学生需要在 $c_{i}c\_i$ 的教室上课。
• 学生可以申请将教室更改为 $d_{i}d\_i$，对于时刻 $ii$ 的申请，有 $p_{i}p\_i$ 的概率申请通过。
• 只能申请更换至多 $mm$ 个时刻的教室。申请是一次性提交的，即无法根据之前的申请通过情况决定接下来申请哪个。
• 教室和教室之间的距离已知。学生一开始在第一节课的教室。课间学生需要走到下一次课的教室。

  • 原题面： 有 $vv$ 个教室，有 $ee$ 条双向道路。通过不同的道路耗费的体力可能不同。 当第 $ii$（$1\le i\le n-11\; \backslash leq\; i\; \backslash leq\; n-1$）节课结束后，牛牛就会从这节课的教室出发，选择一条耗费体力最少的路径前往下一节课的教室。

• 求最小距离总和的期望。

错误思路

• 倒推。
• 令 $dp[i][j][0\mathrm{/}1]dp[i][j][0/1]$ 代表
  • 当前是第 $ii$ 节课，
  • 已经尝试申请（包括第 $ii$ 节课申请的）了 $jj$ 个教室
  • 现在一定位于教室 $c_{i}c\_i$ / $d_{i}d\_i$
  • 从当前教室出发走到最后一个教室的期望。

for (int i=n-1; i>=1; i--)
{
    for (int j=0; j<=min(i,m); j++)
    {
    //不申请当前教室
        //不申请下一个教室
        double tmp1 = dp[i+1][j][0] + 1.0*dis[ ci[i] ][ ci[i+1] ];
        //申请下一个教室
        double tmp2 = (dp[i+1][j+1][0] + 1.0*dis[ ci[i] ][ ci[i+1] ])*(1.0-pi[i+1]) 
                    + (dp[i+1][j+1][1] + 1.0*dis[ ci[i] ][ di[i+1] ])*pi[i+1];
        if(j==m)
            dp[i][j][0] = tmp1;
        else
            dp[i][j][0] = min(tmp1, tmp2);//min(不申请下一个,申请下一个)
        
    //不申请当前教室
        //不申请下一个教室
        tmp1 = dp[i+1][j][0] + 1.0*dis[ di[i] ][ ci[i+1] ];
        //申请下一个教室
        tmp2 = (dp[i+1][j+1][0] + 1.0*dis[ di[i] ][ ci[i+1] ])*(1.0-pi[i+1]) 
            + (dp[i+1][j+1][1] + 1.0*dis[ di[i] ][ di[i+1] ])*pi[i+1];
        if(j==m)
            dp[i][j][1] = tmp1;
        else
            dp[i][j][1] = min(tmp1, tmp2);//min(不申请下一个,申请下一个)
    }
}
double ans = dp[1][0][0];//不申请教室1
if(m >= 1)  //申请教室1
	ans = min(ans, dp[1][1][0]*(1.0-pi[1])+dp[1][1][1]*pi[1]);

• ans=\min \begin{align*} \begin{cases} dp[1][0][0] 不申请教室1\\ dp[1][1][1]\times p_1 + dp[1][1][0]\times (1-p_1)) 教室1 申请通过/不通过 \end{cases} \end{align*}$$
• 上述答案统计方法是错误的。
• Hack 数据：

  n=2, m=3
  dis[1][2] = 1
  

  • 正确答案：0.74（解释：同时申请第1节和第2节是最优的）
  • 实际输出：0.72
• 错误原因：
  • 注意观察第 30 行，答案统计部分。
  • 手动模拟发现，在先前计算 $dp[1][1][0]dp[1][1][0]$ 的时候，因为取了最小值，进行的决策是申请第 2 个教室；但是在计算 $dp[1][1][1]dp[1][1][1]$ 的时候，因为取了最小值，进行的决策是不申请第 2 个教室。
  • 如此统计答案显然是错误的。

正确思路

• 倒推。
• 令 $dp[i][j][0\mathrm{/}1]dp[i][j][0/1]$ 代表
  • 当前是第 $ii$ 节课，
  • 已经尝试申请（包括第 $ii$ 节课申请的）了 $jj$ 个教室
  • $00$：现在位于教室 $c_{i}c\_i$，$11$：申请换了教室，现在可能教室 $d_{i}d\_i$，也可能位于 $c_{i}c\_i$。
  • 从当前教室出发走到最后一个教室的期望。
• 转移分如下情况：
  • $dp[i][j][0]dp[i][j][0]$：在不申请 $ii$ 教室的情况下，考虑教室 $i+1i+1$ 的情况。
  • $dp[i][j][1]dp[i][j][1]$：$\min (\mathrm{申}\mathrm{请}\mathrm{教}\mathrm{室}i+1,\mathrm{不}\mathrm{申}\mathrm{请}\mathrm{教}\mathrm{室}i+1)\backslash min(申请教室i+1,不申请教室i+1)$。对于这两种情况，每一种情况还要讨论 教室 $ii$ 申请是否通过。
• 具体的转移：

  for (int i=n-1; i>=1; i--)
   {
   	for (int j=0; j<=min(i,m); j++)
   	{
   	//0 这一个不申请
   		//下一个不申请
   		double tmp1 = 1.0*dis[ ci[i] ][ ci[i+1] ];
   		//下一个申请
   		double tmp2 = 1.0*dis[ ci[i] ][ ci[i+1] ]*(1.0-pi[i+1])
   					+ 1.0*dis[ ci[i] ][ di[i+1] ]*pi[i+1];
   		if(j==m)
   			dp[i][j][0] = dp[i+1][j][0] + tmp1;
   		else
   			dp[i][j][0] = min(dp[i+1][j][0] + tmp1, dp[i+1][j+1][1]+tmp2);
   		
   	//1 这一个申请
   		//下一个不申请
   		tmp1 = 1.0*dis[ di[i] ][ ci[i+1] ]*pi[i] 
   			 + 1.0*dis[ ci[i] ][ ci[i+1] ]*(1.0-pi[i]);
   		//下一个申请
   		tmp2 = 1.0*dis[ di[i] ][ ci[i+1] ]*pi[i]*(1.0-pi[i+1])
   			 + 1.0*dis[ ci[i] ][ ci[i+1] ]*(1.0-pi[i])*(1.0-pi[i+1])
   			 + 1.0*dis[ di[i] ][ di[i+1] ]*pi[i]*pi[i+1]
   			 + 1.0*dis[ ci[i] ][ di[i+1] ]*(1.0-pi[i])*pi[i+1];
   			
   		if(j==m)
   			dp[i][j][1] = dp[i+1][j][0] + tmp1;
   		else
   			dp[i][j][1] = min(dp[i+1][j][0]+tmp1, dp[i+1][j+1][1]+tmp2);
   		
   		printf("dp%d,%d = %lf,%lf\n",i,j,dp[i][j][0],dp[i][j][1]);
   	}
   }