洛谷P1850 換教室（NOIp2016 Day1 T3）（BZOJ 4720）

期望DP 最短路

洛谷題目傳送門

BZOJ題目傳送門

思路很簡單，先Floyd求出所有教室之間的最短路，然後分情況進行讨論來求解期望值。

但是轉移方程很長。。。

先定義DP數組： f[i][j][0/1] 表示對于前 i 節課，申請修改其中的j節的期望值，其中0表示第 i 節不申請修改，1表示申請。

然後有如下四種情況：

①：第i−1節和第 i 節均不修改。

此時成功的機率為1，期望值為1∗disai−1,ai。

轉移方程：

f[i][j][0]=f[i-1][j][0]+dis[a[i-1]][a[i]];

②：第 i−1 節修改，但第 i 節不修改。

此時成功的機率為proi−1，期望值為 proi−1∗disbi−1,ai ；

失敗的機率為 1−proi−1 ，期望值為 (1−proi−1)∗disai−1,ai 。

轉移方程：

f[i][j][0]=f[i-1][j][1]+pro[i-1]*dis[b[i-1]][a[i]]+(1-pro[i-1])*dis[a[i-1]][a[i]];

f[i][j][0] 的實際取值即為上述兩種情況的較小值。

③：第 i−1 節和第 i 節均修改。

此時i−1和 i 均成功的機率為proi−1∗proi，期望值為 proi−1∗proi∗disbi−1,bi ；

i−1 失敗，但 i 成功的機率為(1−proi−1)∗proi，期望值為 (1−proi−1)∗proi∗disai−1,bi ；

i−1 成功，但 i 失敗的機率為proi−1∗(1−proi)，期望值為 proi−1∗(1−proi)∗disbi−1,ai ；

i−1 和 i 均失敗的機率為(1−proi−1)∗(1−proi)，期望值為 (1−proi−1)∗(1−proi)∗disai−1,ai 。

轉移方程（很長）：

f[i][j][1]=f[i-1][j-1][1]+pro[i]*(pro[i-1]*dis[b[i-1]][b[i]]+(1-pro[i-1])*dis[a[i-1]][b[i]])+(1-pro[i])*(pro[i-1]*dis[b[i-1]][a[i]]+(1-pro[i-1])*dis[a[i-1]][a[i]];           

其實就是把以上的期望值相加，再加上之前的狀态期望值。

④：第 i−1 節不修改，但是第 i 節修改。

此時成功的機率為proi，期望值為 proi∗disai−1,bi ；

失敗的機率為 1−proi ，期望值為 (1−proi)∗disai−1,ai 。

轉移方程：

f[i][j][1]=f[i-1][j-1][0]++pro[i]*dis[a[i-1]][b[i]]+(1-pro[i])*dis[a[i-1]][a[i]];

f[i][j][1] 的實際取值也為上述兩種情況的較小值。

然後就好了。

代碼：

#include<cstdio>
#include<cstring>
#include<algorithm>
#define MAXN 300
#define MAX 2000
using namespace std;
int n,m,p,q;
int a[MAX+5],b[MAX+5],dis[MAXN+5][MAXN+5];
double pro[MAX+5],f[MAX+5][MAX+5][2];
int main(){
    scanf("%d%d%d%d",&p,&q,&n,&m);
    for (int i=1;i<=p;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=p;i++)
        scanf("%d",&b[i]);
    for (int i=1;i<=p;i++)
        scanf("%lf",&pro[i]);
    memset(dis,0x3f,sizeof(dis));
    for (int i=1;i<=n;i++){
        dis[i][i]=0; dis[0][i]=0;
    }
    for (int i=1;i<=m;i++){
        int u,v,d;
        scanf("%d%d%d",&u,&v,&d);
        dis[u][v]=min(dis[u][v],d);
        dis[v][u]=min(dis[v][u],d);
    }
    for (int k=1;k<=n;k++)
        for (int i=1;i<=n;i++)
            for (int j=1;j<=n;j++)
                dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    memset(f,127,sizeof(f));
    f[0][0][0]=0;
    for (int i=1;i<=p;i++){
        f[i][0][0]=f[i-1][0][0]+dis[a[i-1]][a[i]];
        for (int j=1;j<=min(i,q);j++){
            int aa=dis[a[i-1]][a[i]],ab=dis[a[i-1]][b[i]],bb=dis[b[i-1]][b[i]],ba=dis[b[i-1]][a[i]];
            f[i][j][0]=min(f[i-1][j][0]+aa,f[i-1][j][1]+pro[i-1]*ba+(1-pro[i-1])*aa);
            f[i][j][1]=min(f[i-1][j-1][0]+pro[i]*ab+(1-pro[i])*aa,f[i-1][j-1][1]+pro[i]*(pro[i-1]*bb+(1-pro[i-1])*ab)+(1-pro[i])*(pro[i-1]*ba+(1-pro[i-1])*aa));
        }
    }
    double ans=0x7fffffff;
    for (int i=0;i<=q;i++)
        ans=min(ans,min(f[p][i][1],f[p][i][0]));
    printf("%.2lf",ans);
    return 0;
}