题解- NOIPDay1T3 换教室

题目意思

题面很长但是挺好懂的。就是你有次换课机会从班级转换到班级，但是只有的概率能够成功转换，代价就是到的最短路。问你期望总和最小是多少？

主要用到的算法为最短路以及动态规划

  • 最短路

就是求出任意两个点之间存在的最短路距离，用就可以求解，所以能过的

  • 动态规划

首先我们要明确状态

表示到第间教室用了次转换机会第次选或不选的最优解

初始化：

转移：

非常刺激的！首先存在两种大可能即第次使不使用转换技能。然后再对这两种情况讨论：

对于

  • 就是次你不使用技能，那么转移有一种小情况：

  • 就是你次使用技能啦，又分两种小情况

    • 申请成功了：
      因为申请成功从转移到

    • 申请不成功：
      因为申请不成功的概率为

  • 于是将上述两种情况综合在一起则为：

对于

  • 就是次你不使用技能，那么转移有两种小情况

    • 第次申请成功啦：

    • 第次申请失败啦：

      这个应该比较好理解就是如果你申请成功那么一定是由上次的到这次的否则还是

  • 就是次你使用技能，那么转移有四种小情况

    • 次成功次失败：
    • 次成功次成功：
    • 次失败次成功：
      • 次失败次失败：

  • 于是将上述两种情况综合在一起则为：

转移相当得长但是很好理解qwq

#include <bits/stdc++.h>
using namespace std;

struct IO {
    #define gc getchar
    #define pt putchar

    inline int read() {
        int sum=0,ff=1; char ch=gc();
        while(!isdigit(ch)) {
            if(ch=='-') ff=-1;
            ch=gc();
        }
        while(isdigit(ch))
            sum=sum*10+(ch^48),ch=gc();
        return sum*ff;
    }

    inline void write(int x) {
        if(x<0)
            pt('-'),x=-x;
        if(x>9)
            write(x/10);
        pt(x%10+48);
    }

    inline void writeln(int x) {
        write(x);
        pt('\n');
    }
} fast;

#define inf 1e8
#define db double 
const int maxn=2333;

int n,m,V,E,cnt;
int dis[maxn][maxn],c[maxn],d[maxn];
double p[maxn],f[maxn][maxn][3],ans;

int main() {
//    freopen("classroom.in","r",stdin);
//    freopen("classroom.out","w",stdout);
    n=fast.read();
    m=fast.read();
    V=fast.read();
    E=fast.read();
    for ( int i=1;i<=n;i++ ) c[i]=fast.read();
    for ( int i=1;i<=n;i++ ) d[i]=fast.read();
    for ( int i=1;i<=n;i++ ) scanf("%lf",&p[i]);

    for ( int i=1;i<=V;i++ )
        for ( int j=1;j<i;j++ )
            dis[i][j]=dis[j][i]=inf;
    for ( int i=1;i<=E;i++ ) { 
        int u=fast.read();
        int v=fast.read();
        int z=fast.read();
        dis[u][v]=min(dis[u][v],z);
        dis[v][u]=dis[u][v];
    }

    for ( int k=1;k<=V;k++ ) 
        for ( int i=1;i<=V;i++ ) 
            for ( int j=1;j<i;j++ ) 
                if(dis[i][j]>dis[i][k]+dis[k][j])
                    dis[j][i]=dis[i][j]=dis[i][k]+dis[k][j];

    for ( int i=1;i<=n;i++ ) 
        for ( int j=0;j<=m;j++ ) 
            f[i][j][0]=f[i][j][1]=inf;
    f[1][0][0]=f[1][1][1]=0;

    for ( int i=2;i<=n;i++ ) 
        for ( int j=0;j<=m;j++ ) {

            double casea=f[i-1][j][0]+(db)dis[c[i-1]][c[i]];
            double caseb=f[i-1][j][1]+p[i-1]*(db)dis[d[i-1]][c[i]];
            double casec=(1-p[i-1])*(db)dis[c[i-1]][c[i]];
//            printf("casea=%.3lf caseb=%.3lf casec=%.3lf\n",casea,caseb,casec);
            f[i][j][0]=min(casea,caseb+casec);

            if(j!=0) {
                double case1=f[i-1][j-1][1]+(p[i]*p[i-1])*(db)dis[d[i-1]][d[i]];
                double case2=(p[i]*(1-p[i-1]))*(db)dis[c[i-1]][d[i]];
                double case3=((1-p[i])*p[i-1])*(db)dis[d[i-1]][c[i]];
                double case4=((1-p[i])*(1-p[i-1]))*(db)dis[c[i-1]][c[i]];
                double case5=f[i-1][j-1][0]+p[i]*(db)dis[c[i-1]][d[i]];
                double case6=(1-p[i])*(db)dis[c[i-1]][c[i]];
                f[i][j][1]=min(case1+case2+case3+case4,case5+case6); 
            }
        }
    ans=inf;
//    for ( int i=0;i<=m;i++ ) 
//        printf("%.3lf %.3lf\n",f[n][i][0],f[n][i][1]);

    for ( int i=0;i<=m;i++ ) 
        ans=min(ans,min(f[n][i][0],f[n][i][1]));
    printf("%.2lf\n",ans);
    return 0;
}