Luogu_P1850 换教室 DP+期望

Luogu_P1850 换教室

### DP+期望

题目链接

考虑DP
设\(f[i][j][0/1]\)为从\(1\)到\(i\)交换\(j\)个(不一定成功)，当前换或者不换的耗费体力值的总和的期望
先用floyd把任意两点之间的距离求出
然后进行DP
分当前点选与不选进行分类
具体看注释

---

代码和注释如下：

#include<bits/stdc++.h>
using namespace std;
const int maxn=2010;
int n,m,v,e;
int ci[maxn],di[maxn];
double p[maxn],tu[500][500],f[maxn][maxn][2];
int main()
{
    scanf("%d%d%d%d",&n,&m,&v,&e);
    for(int i=1;i<=n;i++) scanf("%d",&ci[i]);
    for(int i=1;i<=n;i++) scanf("%d",&di[i]);
    for(int i=1;i<=n;i++) scanf("%lf",&p[i]);
    for(int i=1;i<=v;i++) for(int j=1;j<=v;j++) tu[i][j]=0x3f3f3f3f;
    for(int i=1;i<=v;i++) tu[i][i]=0;
    for(int x,y,i=1;i<=e;i++){
        double z;scanf("%d%d%lf",&x,&y,&z);
        tu[x][y]=min(tu[x][y],z);tu[y][x]=tu[x][y];
    }
    for(int k=1;k<=v;k++) for(int i=1;i<=v;i++) for(int j=1;j<=v;j++)
        tu[i][j]=min(tu[i][j],tu[i][k]+tu[k][j]);
    for(int i=1;i<=n;i++) for(int j=0;j<=m;j++) for(int k=0;k<=1;k++)
        f[i][j][k]=0x3f3f3f3f;
    f[1][0][0]=0.0;f[1][1][1]=0.0;
    for(int i=2;i<=n;i++) for(int j=0;j<=m && j<=i;j++){
        //这次不选
        f[i][j][0]=min(f[i-1][j][0]+tu[ci[i-1]][ci[i]],//上一次没选
            f[i-1][j][1]+tu[ci[i-1]][ci[i]]*(1.0-p[i-1])+tu[di[i-1]][ci[i]]*p[i-1]);//上一个选了
        if(j>=1){
            //这次选
            f[i][j][1]=min(f[i-1][j-1][0]+tu[ci[i-1]][di[i]]*p[i]//上一次没选，这次成功了的期望
                +tu[ci[i-1]][ci[i]]*(1.0-p[i]),//上次没选，这次没成功的期望
                f[i-1][j-1][1]+tu[di[i-1]][di[i]]*p[i]*p[i-1]//上次选了，这两次都成功了
                +tu[di[i-1]][ci[i]]*p[i-1]*(1.0-p[i])//上次选了，上一次成功，这次失败
                +tu[ci[i-1]][di[i]]*(1.0-p[i-1])*p[i]//上次选了，上次失败，这次成功
                +tu[ci[i-1]][ci[i]]*(1.0-p[i-1])*(1.0-p[i]));//上次选了，都失败
        }
    }
    double ans=0x3f3f3f3f;
    for(int i=0;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1]));
    printf("%.2lf",ans);
    return 0;
}