NOIP2016换教室

NOIp级的概率期望（然而我现在还是需要推第二遍）。

可以得到很简单的$dp$定义，$dp[i][j][0/1]$，考虑完前$i$个时间段，进行了$j$次申请，当前这次是否申请的最优期望。

剩下的转移可以直接分类讨论：

dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1-p[i-1])*dis[c[i-1]][c[i]])，由于这一次我们没有申请，所以当上一次也没有申请的时候只有一种情况，从上个c到这个c，当上一次申请后，讨论申请是否成功，转移的距离随着是否成功而变。

dp[i][j][1]=min(dp[i-1][j-1][0]+p[i]*dis[c[i-1]][d[i]]+(1-p[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i-1]][d[i]]+p[i-1]*(1-p[i])*dis[d[i-1]][c[i]]+(1-p[i-1])*p[i]*dis[c[i-1]][d[i]]+(1-p[i-1])*(1-p[i])*dis[c[i-1]][c[i]]，式子很长，但是思想是一样的，讨论是否成功，来决定dis的下标选择。

dis数组可以直接$Floyd$解出来。

有些小细节，点数300，边数90000，明示重边，注意$Floyd$不要打丑。

最优决策$dp$注意初始化问题。

代码是最后一周写的，完全放飞自我的压行，看看$dp$式子就完事了。（注意保护眼睛）

#include<bits/stdc++.h>

using namespace std;

inline int read(int sum=0,int f=1,char x=getchar()){
    while(x<'0' || x>'9'){
        if(x=='-') f=-1; x=getchar();
    }while(x>='0' && x<='9'){
        sum=sum*10+x-'0';x=getchar();
    }return sum*f;
}

int n,m,V,E,c[2050],d[2050],dis[305][305];
double p[2050],dp[2050][2050][2],ans=1e14;

int main(){
    n=read(); m=read(); V=read(); E=read();
    for(int i=1; i<=n; ++i) c[i]=read(); for(int i=1; i<=n; ++i) d[i]=read(); for(int i=1; i<=n; ++i) scanf("%lf",p+i);
    memset(dis,0x3f,sizeof(dis)); for(int i=1; i<=V; ++i) dis[i][i]=0;
    for(int i=1,x,y,w; i<=E; ++i) x=read(), y=read(), w=read(), dis[x][y]=min(dis[x][y],w), dis[y][x]=min(dis[y][x],w);
    for(int k=1; k<=V; ++k) for(int i=1; i<=V; ++i) for(int j=1; j<=V; ++j) dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
    memset(dp,88,sizeof(dp)); dp[0][0][0]=dp[0][0][1]=0; for(int i=0; i<=V; ++i) dis[i][0]=dis[0][i]=0;
    for(int i=1; i<=n; ++i) for(int j=0; j<=min(i,m); ++j){
            dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],dp[i-1][j][1]+p[i-1]*dis[d[i-1]][c[i]]+(1.0-p[i-1])*dis[c[i-1]][c[i]]);
            if(j) dp[i][j][1]=min(dp[i-1][j-1][0]+p[i]*dis[c[i-1]][d[i]]+(1.0-p[i])*dis[c[i-1]][c[i]],dp[i-1][j-1][1]+p[i-1]*p[i]*dis[d[i-1]][d[i]]+p[i-1]*(1.0-p[i])*dis[d[i-1]][c[i]]+(1.0-p[i-1])*p[i]*dis[c[i-1]][d[i]]+(1.0-p[i-1])*(1.0-p[i])*dis[c[i-1]][c[i]]);
        }
    for(int i=0; i<=m; ++i) ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2lf",ans); return 0;
}