【正经题解】换教室

期望的计算:如果概率为 $k$ 的代价为 $w1$ ,概率为( $1-k$ )的代价为 $w2$ ，那么期望就是概率乘代价，即
$k$ * $w1+$ ( $1-k$ )* $w2$
$n$ 个时段的期望等于每个时段的期望之和，显然的.
于是我们来看这个题
首先有最短路， $floyed$ 暴力预处理 $x$ 和 $y$ 之间的距离 $dis$ [ $x$ ][ $y$ ]
假如到 $i-1$ 个时段已经走了距离 $d$ ，那么有可以选择换和不换第 $i$ 个时段的教室
如果不换，那么显然这一时段的教室只能为 $ci$
这时上一次分为换和不换两种情况，教室有 $k$ [ $i-1$ ]的概率为 $di$ 和( $1-k$ [ $i-1$ ])的概率为 $ci$
期望按上面的算就好,教室之间的 $dis$ 乘上概率
如果换第 $i$ 个时段的教室，那么有 $k$ [ $i$ ]的概率为 $di$ 和( $1-k$ [ $i$ ])的概率为 $ci$
然后上一次的同理
这个时候有 $k$ [ $i$ ] $k$ [ $i-1$ ]的概率两个教室分别为 $di$ 和 $d$ [ $i-1$ ]
剩下的情况同理
于是我们设 $f$ [ $i$ ][ $j$ ][ $k$ ]为到第 $i$ 个时段已经换了 $j$ 个教室的期望， $k$ 描述这一次换不换，为 $0$ 换，为 $1$ 不换
于是状态转移方程很容易写出
按照上面的描述就好
具体的可以看代码
初值， $f$ [ $1$ ][ $1$ ][ $1$ ] $=f$ [ $1$ ][ $0$ ][ $0$ ] $=0$ ,其它为 $inf$ ，很好理解
答案就是 $max$ { $f$ [ $n$ ][ $i$ ][ $k$ ]}, $i=0$ ... $m$ , $k=0$ ... $1$

#include<cstdio>
#include<iostream>
using namespace std;
const int inf=1<<20;//
int n,m,v,e,a[2001],b[2001],dis[2001][2001];
double ans,f[2001][2001][2],c[2001];
inline char gc()//fread加速快读
{
    static char BB[1000001],*S=BB,*T=BB;
    return S==T&&(T=(S=BB)+fread(BB,1,1000000,stdin),S==T)?EOF:*S++;
}
inline int getin()//普通快读
{
    int x=0;char ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')x=x*10+ch-48,ch=gc();
    return x;
}
inline double rgetin()//仿照负数快读写实数快读
{
    double x=0;char ch=gc();
    while(ch<'0'||ch>'9')ch=gc();
    while(ch>='0'&&ch<='9')x=x*10+(ch-48),ch=gc();
    if(ch=='.')
    {
        double l=0.1;
        ch=gc();
        while(ch>='0'&&ch<='9')x=x+(ch-48)*l,l/=10,ch=gc();
    }
    return x;
}
int main()
{
    n=getin(),m=getin(),v=getin(),e=getin();
    for(register int i=1;i<=n;i++)a[i]=getin();//不换的教室
    for(register int i=1;i<=n;i++)b[i]=getin();//换的教室
    for(register int i=1;i<=n;i++)c[i]=rgetin();//概率
    for(register int i=1;i<=v;i++)
        for(register int j=1;j<i;j++)
            dis[i][j]=dis[j][i]=inf;//dis初始为inf，不用处理dis[i][i]的情况
    for(register int i=1;i<=e;i++)
    {
        register int x,y,w;//从x到y有一条权值为w的边
        x=getin(),y=getin(),w=getin(),dis[x][y]=dis[y][x]=min(dis[x][y],w);//无向图，防止重边
    }
    for(register int k=1;k<=v;k++)
        for(register int i=1;i<=v;i++)
            for(register int j=1;j<i;j++)//无向图，所以不用处理j>=i
                if(dis[i][k]+dis[k][j]<dis[i][j])
                    dis[i][j]=dis[j][i]=dis[i][k]+dis[k][j];
    for(register int i=1;i<=n;i++)
        for(register 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(register int i=2;i<=n;i++)
    {
        register int mn=min(i,m);
        register double w1=dis[a[i-1]][a[i]],
        w2=dis[b[i-1]][a[i]]*c[i-1]+dis[a[i-1]][a[i]]*(1-c[i-1]),
        w3=dis[a[i-1]][b[i]]*c[i]+dis[a[i-1]][a[i]]*(1-c[i]),
        w4=dis[a[i-1]][a[i]]*(1-c[i-1])*(1-c[i])+dis[a[i-1]][b[i]]*(1-c[i-1])*c[i]+dis[b[i-1]][a[i]]*(1-c[i])*c[i-1]+dis[b[i-1]][b[i]]*c[i-1]*c[i];//预先算好加速，这是一个很不好看的递推式
        for(register int j=0;j<=mn;j++)
        {
            f[i][j][0]=min(f[i-1][j][0]+w1,f[i-1][j][1]+w2);
            if(j)f[i][j][1]=min(f[i-1][j-1][0]+w3,f[i-1][j-1][1]+w4);
        }//正常的dp
    }
    ans=inf;
    for(register int i=0;i<=m;i++)
        ans=min(ans,min(f[n][i][0],f[n][i][1]));//统计答案
    printf("%.2lf",ans);
}