分类： 数学

一道优\(d\acute{u}\)秀\(li\acute{u}\)的期望DP。
简述题意：
原有一个包括\(n\)个节点的路径，你可以用\(m\)次操作，每一次操作可以把第\(i\)个节点从\(c_{i}\)换到\(b_{i}\)。
对于每一次操作，有\(p_{i}\)的概率成功。求最优决策下路径长度的期望。

首先考虑到是稠密图，故考虑用邻接矩阵来处理。不过需要注意读入时应当取较小值，以及每个点到其本身的距离为\(0\)
首先用\(Floyd\)预处理出所有点之间的距离。然后我们定义\(f_{i,j,k}\)表示，当前在决定第\(i\)个节点，已经使用了\(j\)次机会，当前选择为\(k\)时的期望路径长度。
那么我们考虑转移。
对于每一个状态，我们有两种选择：使用机会或者不使用机会。故而我们尝试推理状态转移方程：
首先，如果不使用机会的话，有两种情况可以转移过来，分别是，上一次使用了机会，或者上一次没有使用机会，故：
$$f_{i,j,0}=Min(f_{i-1,j,0}+mp_{c_{i-1},c_{i}},$$
$$f_{i-1,j,1}+mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}));$$
如果在这个点使用机会且成功的话，则有：
$$f_{i,j-1,1}=Min(f_{i-1,j-1,0}+mp_{c_{i-1},d_{i}}*p_{i}+mp_{c_{i-1},c_{i}}*(1-p_{i}),$$
$$f_{i-1,j-1,1}+m(p_{d_{i-1},d_{i}}*p_{i-1}+mp_{c_{i-1},d_{i}}*(1-p_{i-1}))*p_{i}+$$
$$(mp_{d_{i-1},c_{i}}*p_{i-1}+mp_{c_{i-1},c_{i}}*(1-p_{i-1}))*(1-p_{i});$$
然后，只需要走到终点即可，因此:
$$ Ans=Min(f_{N,i,j})\ (i\in [0,M],j\in [0,1])$$

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define Min(_A,_B) ((_A)<(_B)?(_A):(_B))
int mp[305][305],N,M,V,E;
int c[2005],d[2005];
double p[2005],f[2005][2005][2];
void init(){
    memset(mp,0x3f,sizeof(mp));
    scanf("%d%d%d%d",&N,&M,&V,&E);
    for(int i=1;i<=N;++i){
        scanf("%d",&c[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%d",&d[i]);
    }
    for(int i=1;i<=N;++i){
        scanf("%lf",&p[i]);
    }
    int u,v,w;
    for(int i=1;i<=E;++i){
        scanf("%d%d%d",&u,&v,&w);
        mp[u][v]=Min(mp[u][v],w),mp[v][u]=Min(mp[u][v],w);
    }
    for(int i=1;i<=V;++i){
        mp[i][i]=0;
    }
    for(int k=1;k<=V;++k){
        for(int i=1;i<=V;++i){
            for(int j=1;j<=V;++j){
                mp[i][j]=Min(mp[i][j],mp[i][k]+mp[k][j]); 
            }
        }
    }
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<=1;++k){
                f[i][j][k]=1000007;
            }
        }
    }
    f[1][0][0]=f[1][1][1]=0;
    for(int i=2;i<=N;++i){
        for(int j=0;j<=M;++j){
            f[i][j][0]=Min(f[i-1][j][0]+mp[c[i-1]][c[i]],f[i-1][j][1]+mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]));
            if(!j){
                continue;
            }
            f[i][j][1]=Min(f[i-1][j-1][0]+mp[c[i-1]][d[i]]*p[i]+mp[c[i-1]][c[i]]*(1-p[i]),f[i-1][j-1][1]+(mp[d[i-1]][d[i]]*p[i-1]+mp[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+(mp[d[i-1]][c[i]]*p[i-1]+mp[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i]));
        }
    }
    double ans=1000007;
    for(int i=0;i<=M;++i){
        for(int j=0;j<2;++j){
            ans=Min(ans,f[N][i][j]);
        }
    }
    /*
    for(int i=1;i<=N;++i){
        for(int j=0;j<=M;++j){
            for(int k=0;k<2;++k){
                printf("%.2lf ",f[i][j][k]);
            }
            printf("|");
        }
        puts("");
    }
    */
    printf("%.2lf",ans);
}
int main(){
    init();
    return 0;
}