BZOJ 4720 换教室

题目大意

给你一堆课程，每个课程可以选择在默认教室上课（即不换课）或申请去另一指定教室上课（换课），教室之间有距离，申请换课有一定成功率，问最小移动距离期望。

期望DP.

设$f_{i,j}$表示$i$天换$j$节课本天不换课的移动期望，$g_{i,j}$表示$i$天换$j$节课本天换课的移动期望，所以有一个很长的DP式子：

$f_{i,j}=\min(f_{i-1,j}+dis_{a_{i-1} \to a_j},g_{i-1,j}+dis_{b_{i-1} \to a_{i}} * p_{i-1}+dis_{a_{i-1} \to a_j} * (1-p_{i-1}))$

$g_{i,j}=\min(f_{i-1,j-1}+dis_{a_{i-1} \to b_i}p_i+dis_{a_{i-1} \to a_i}(1-p_i) , g_{i-1,j-1} + dis_{b_{i-1} \to b_i} * p_{i-1} * p_i + \ \ \ \ \ \ \ \ \ \ \ \ dis_{a_{i-1} \to b_i} * (1-p_{i-1}) * p_i + dis_{b{i-1} \to a_i} * p_{i-1} * (1-p_i) + dis_{a_{i-1} \to a_i} * (1-p_{i-1})*(1-p_i))$

dalao说这是大水题……

就是一个十分普通的概率期望DP……（我居然当时认为很难)

而我当时的想法是$f_{i,j}$表示$i$天$j$课程在主教室上课的期望，$g_{i,j}$表示$i$天$j$次换课在次教室上课的期望……

%%%WH太强辣

#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,v,m,e;
int a[2010],b[2010],inx,iny,inz,dis[310][310];
double p[2010],f[2010][2010],g[2010][2010],ans=100000000.0;
inline void floyd()
{
    for(register int i=1;i<=v;++i) dis[i][i]=0;
    for(register int k=1;k<=v;++k)
        for(register int i=1;i<=v;++i)
            for(register int j=1;j<=v;++j)
                    dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
int main()
{
    memset(dis,0x3f,sizeof dis);
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(register int i=1;i<=n;++i) scanf("%d",a+i);
    for(register int i=1;i<=n;++i) scanf("%d",b+i);
    for(register int i=1;i<=n;++i) scanf("%lf",p+i);
    for(register int i=1;i<=e;++i) scanf("%d%d%d",&inx,&iny,&inz),dis[inx][iny]=dis[iny][inx]=min(dis[inx][iny],inz);
    floyd();
    for(register int i=0;i<=n;++i)
        for(register int j=0;j<=m;++j)
            f[i][j]=g[i][j]=100000000.0;
    f[1][0]=g[1][1]=0;
    for(register int i=2;i<=n;++i)
    {
        int maxj=min(i,m);
        for(register int j=0;j<=maxj;++j)
        {
            f[i][j]=min(f[i-1][j]+dis[a[i-1]][a[i]],g[i-1][j]+dis[b[i-1]][a[i]]*p[i-1]+dis[a[i-1]][a[i]]*(1-p[i-1]));
            if(j) g[i][j]=min(f[i-1][j-1]+dis[a[i-1]][b[i]]*p[i]+dis[a[i-1]][a[i]]*(1-p[i]), g[i-1][j-1] + dis[b[i-1]][b[i]]*p[i-1]*p[i] + dis[a[i-1]][b[i]]*(1-p[i-1])*p[i] + dis[b[i-1]][a[i]]*p[i-1]*(1-p[i]) + dis[a[i-1]][a[i]]*(1-p[i-1])*(1-p[i]));
        }
    }
    for(register int i=0;i<=m;++i) ans=min(ans,min(f[n][i],g[n][i]));
    printf("%.2lf\n",ans);
    return 0;
}