题解 P1850 【换教室】

· · 题解

$\rm{First}$ $\rm{of}$ $\rm{all}$ , 我自认为这篇题解写的比大佬们要详细……比较适合提高组的新手$OIer$阅读$qwq

嗯，这是我的第一篇期望的题解……这是本蒟蒻第一次一眼看出DP方程和预处理qwq，纪念一下！

但实际上，是rqy帮我解决的这道题的关键部分……此致敬礼qwq

那么对于这篇题解，我的定义是，没有什么优化，只是最简单的求解这个问题而已。至于优化什么的，本蒟蒻不会呀qwq.

那么对于这道题而言，先捋清楚题目是求什么的吧：

对于这个无向连通图，我们将每走一步定义为一个阶段。那么每一个阶段都有两种可能性：p_i的概率去d_i，但是在所有的d[i] 中(1<=i<=n)至多可以走m个，(1-p_i)的概率去c[i]。而我们要求的，就是在这n个阶段结束之后的路程最小期望。

那么其实状态之间的转移，我们不难看出有两种状态的转移：从d[i-1]或从c[i-1]转移过来。而因为实际上对于这个DP而言，因为数据不大，所以不需要优化什么的qwq，记录每种状态是可行的。

那么很显然啊，我们首先要预处理出每两个点之间的最短路来，方便状态的转移。而在这里，最简单的就是Floyd啊qwq。(n^3显然可以接受)

    for(qwq int k=1;k<=v;k++)
      for(qwq int i=1;i<=v;i++)
        for(qwq int j=1;j<i;j++)
          if(f[i][k]+f[k][j]<f[i][j])
             f[i][j]=f[j][i]=f[i][k]+f[k][j];

然后就是DP方程了:

我们定义dp[i][j][0/1]来表示当前为第i个阶段，连同这一次已经用了j次换教室的机会，当前这次换(1)不换(0)的最小期望路程总和。

那么转移就可以如此转移：

这次不换：

dp[i][j][0]=$ $min($上次不换的$dp+$这两次之间的路程 $~~$， $~~$上次概率换了之后的$dp+p[i - 1]\times$上次换了的教室与这次不换的教室之间的距离$+(1-p[i - 1])\times$上次不换的教室与这次不换的教室之间的距离$)

“诶，为什么上次概率换了之后（即逗号之后的一大串）要加两个期望啊？”

这个问题就是rqy大佬给我解决的，现在我要农夫山泉一把了：因为在上一次换教室时是“概率”交换，所以不一定会换呀。所以要把两种情况的都加上qwq。

到这儿我们就可以发现，其实换教室比不换教室是要多一重状态的，因为换教室总要牵扯“概率成功”的问题qwq

那其实接下来的状态转移方程就很简单了：一次换一次不换，遇到不换就(1-p[i])，遇到换就p[i]；两次都不换就不用枚举概率。而且由于牵扯到两次都是概率性事件（比如两次都换）之类的，这个时候需要的就是乘法原理了。

那么DP即如下：

#define qwq register 
for(qwq int i=2;i<=n;i++){
     double add1=f[c[i-1]][c[i]];
      for(qwq int j=0;j<=min(m,i);j++)
       {                     
          dp[i][j][0]=min(dp[i-1][j][0]+add1,dp[i-1][j][1]+f[d[i-1]][c[i]]*p[i-1]+f[c[i-1]][c[i]]*(1-p[i-1]));
          if(j!=0)
          dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*p[i]+f[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+f[c[i-1]][d[i]]*(1-p[i-1])*p[i]+f[d[i-1]][c[i]]*(1-p[i])*p[i-1]+f[d[i-1]][d[i]]*p[i-1]*p[i]);
       }   
    }

总结：遇到期望的题目时一定要全面考虑啊！我们可以发现这个题的dp方程其实并不难想。

完结撒花！

//感谢rqy大佬qwqqq 
#include<iostream>
#include<cstdio>
#define qwq register 
using namespace std;
double p[10001],f[2001][2001],dp[2001][2001][2];
int a[2001][2001],c[20001],d[20001];
inline double min(double a,double b){
    return a<b?a:b;
}
inline int  qread(){
    int  k = 0;
    char c;
    c = getchar();
    while(!isdigit(c))c = getchar();
    while(isdigit(c)){
        k = (k<<1)+(k<<3)+c-48;
        c = getchar();
    }
    return k ;
}
int main()
{
    int n,m,v,e,a1,b1,c1;
    cin>>n>>m>>v>>e;
    for(qwq int i=1;i<=n;i++)c[i]=qread();
    for(qwq int i=1;i<=n;i++)d[i]=qread();
    for(qwq int i=1;i<=n;i++)cin>>p[i];

    for(qwq int i=1;i<=v;i++)
     for(qwq int j=1;j<i;j++)
      f[i][j]=f[j][i]=999999999;

    for(qwq int i=1;i<=e;i++){
        a1=qread(),b1=qread(),c1=qread();
        f[a1][b1]=f[b1][a1]=min(f[a1][b1],c1);
    }

    for(qwq int k=1;k<=v;k++)
      for(qwq int i=1;i<=v;i++)
        for(qwq int j=1;j<i;j++)
          if(f[i][k]+f[k][j]<f[i][j])
             f[i][j]=f[j][i]=f[i][k]+f[k][j];

    for(qwq int i=1;i<=n;i++)
        for(qwq int j=0;j<=m;j++)
            dp[i][j][0]=dp[i][j][1]=999999999;

    dp[1][0][0]=dp[1][1][1]=0;
    for(qwq int i=2;i<=n;i++){
     double add1=f[c[i-1]][c[i]];
      for(qwq int j=0;j<=min(m,i);j++)
       {                     
          dp[i][j][0]=min(dp[i-1][j][0]+add1,dp[i-1][j][1]+f[d[i-1]][c[i]]*p[i-1]+f[c[i-1]][c[i]]*(1-p[i-1]));
          if(j!=0)
          dp[i][j][1]=min(dp[i-1][j-1][0]+f[c[i-1]][d[i]]*p[i]+f[c[i-1]][c[i]]*(1-p[i]),dp[i-1][j-1][1]+f[c[i-1]][c[i]]*(1-p[i-1])*(1-p[i])+f[c[i-1]][d[i]]*(1-p[i-1])*p[i]+f[d[i-1]][c[i]]*(1-p[i])*p[i-1]+f[d[i-1]][d[i]]*p[i-1]*p[i]);
       }   
    }          

    double hahaha=9999999999;
    for(int i=0;i<=m;i++){
    hahaha=min(dp[n][i][0],min(dp[n][i][1],hahaha));}
    printf("%.2lf",hahaha);
}

By Flower _ pks