期望DP get ！

A4paper · 2018-10-30 16:02:26 · 个人记录

提高：

传送门

经典题目，超长期望 DP

首先要跑一遍 Floyed 求出最短路（记得判重边）

然后就是 DP ，其实只要把情况考虑全，方程好想，

定义 f[i][j][1/0] 表示在第 i 阶段，已经用了 j 次机会，这一次换 (1) 或不换 (0) 的最小期望。

对于 f[i][j][0] ，有两种情况：

1. 上一次没换，状态为： f[i-1][j][0]+map[c[i-1]][c[i]]

   即上一次的期望路程加上到下一间教室的路程。

2. 上一次换了，状态为： f[i-1][j][1]+map[d[i-1]][c[i]]*k[i]+map[c[i-1]][c[i]]*(1-k[i])

   这时要把换成功和不成功的期望全算上。

对于 f[i][j][1] ，就开始变态了：

1. 上一次没换，状态为： f[i-1][j-1][0]+map[c[i-1]][d[i]]*k[i]+map[c[i-1]][c[i]]*(1-k[i])

   同样也是要把成功和不成功的期望都算上。

2. 上一次换了，就要考虑上一次成不成功：f[j-1][1]

   +map[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i]) +map[c[i-1]][d[i]]*(1-k[i-1])*k[i] +map[d[i-1]][c[i]]*k[i-1]*(1-k[i]) +map[d[i-1]][d[i]]*k[i]*k[i-1])

   这时考虑了上次有没有换成功和这次有没有换成功，一共是四种情况。

int n,m,v,e;
double ans=INF;
int c[MAXN],d[MAXN];
int map[MAXN][MAXN];
double k[MAXN];
double f[MAXN][2];

void Floyed()
{
    for(int i=1;i<=v;i++)
    for(int j=1;j< i;j++)
        map[i][j] = map[j][i] = INF;
    for(int i=1;i<=e;i++)
    {
        int a,b,w;
        cin >> a >> b >> w;
        map[a][b] = map[b][a] = min(map[a][b],w);
    }
    for(int k=1;k<=v;k++)
    for(int i=1;i<=v;i++)
    for(int j=1;j< i;j++)
        map[i][j] = map[j][i] = min(map[i][j],map[i][k]+map[k][j]);
}

int main(void)
{
    cin >> n >> m >> v >> e;
    for(int i=1;i<=n;i++) cin >> c[i];
    for(int i=1;i<=n;i++) cin >> d[i];
    for(int i=1;i<=n;i++) cin >> k[i];
    Floyed();
    for(int i=1;i<=n;i++)
    for(int j=0;j<=m;j++)
        f[j][0] = f[j][1] = INF;
    f[0][0] = f[1][1] = 0;
    for(int i=2;i<=n;i++)
    for(int j=min(i,m);j>=0;j--)
    {
        f[j][0]=min(f[j][0]+map[c[i-1]][c[i]],
                    f[j][1]+map[d[i-1]][c[i]]*k[i-1]+map[c[i-1]][c[i]]*(1-k[i-1]));
        if(j != 0)
        f[j][1]=min(f[j-1][0]+map[c[i-1]][d[i]]*k[i]+map[c[i-1]][c[i]]*(1-k[i]),
                    f[j-1][1]+map[c[i-1]][c[i]]*(1-k[i-1])*(1-k[i])+
                             +map[c[i-1]][d[i]]*(1-k[i-1])*k[i]+
                             +map[d[i-1]][c[i]]*k[i-1]*(1-k[i])+
                             +map[d[i-1]][d[i]]*k[i]*k[i-1]);
    }
    for(int j=0;j<=m;j++)
        ans = min(ans,min(f[j][0],f[j][1]));
    printf("%.2lf",ans);
    return 0;
}