[洛谷 1850][NOIP2016]换教室

题目链接

https://www.luogu.org/problem/P1850

题解

一道状态转移方程很长的期望题。

首先，我们要预处理任意两个教室间的最短路径，因为 \(v \leq 300\)，所以用 floyd 搞就好了。

接下来就是状态转移的过程啦。我们用 \(f(i,j,0/1)\) 表示当前处理到了第 \(i\) 节课，用掉了 \(j\) 次换教室机会，这一次是否换教室（没换为 \(0\)，换了为 \(1\)）这一状态下的最小期望值。

接下来有很多种情况：（式子有些长，下面是文字叙述，具体式子可以在代码里面看）

1. 这节课没有申请换教室：
   1. 前一节课也没申请：在前一状态 \(f(i-1,j,0)\) 的基础上加上路程期望值（没换教室的话概率显然为 \(1\)）；
   2. 前一节课申请了：在前一状态 \(f(i-1,j,1)\) 的基础上加上前一课程申请成功的路程期望值和申请失败的路程期望值。
2. 这节课申请换教室：
   1. 前一节课没有申请：在前一状态 \(f(i-1,j-1,0)\) 的基础上加上当前课程申请成功的路程期望值和申请失败的路程期望值；
   2. 前一节课申请了：这个就比较复杂了，因为有四种情况，两个申请均通过，前一申请成功而后一申请失败，前一申请失败而后一申请成功，两个申请都失败。要在前一状态 \(f(i-1,j-1,1)\) 的基础上分别加上这四种事件的路程期望值。

这样我们就解决了本题。

#include <cstdio>
#include <cstring>
#include <algorithm>
#define INF 0x3f3f3f3f
using namespace std;
int c[2005],d[2005],dist[305][305];
double k[2005],f[2005][2005][2];
int main()
{
 int n,m,v,e;
 memset(dist,INF,sizeof(dist));
 scanf("%d%d%d%d",&n,&m,&v,&e);
 for(int i=1;i<=n;i++)
  scanf("%d",&c[i]);
 for(int i=1;i<=n;i++)
  scanf("%d",&d[i]);
 for(int i=1;i<=n;i++)
  scanf("%lf",&k[i]);
 for(int i=1;i<=e;i++)
 {
  int a,b,w;
  scanf("%d%d%d",&a,&b,&w);
  dist[a][b]=dist[b][a]=min(dist[a][b],w);
 }
 for(int i=1;i<=v;i++)
  dist[i][i]=0;
 for(int k=1;k<=v;k++)
  for(int i=1;i<=v;i++)
   for(int j=1;j<=v;j++)
    dist[i][j]=min(dist[i][j],dist[i][k]+dist[k][j]);
 for(int i=1;i<=n;i++)
  for(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(int i=2;i<=n;i++)
  for(int j=0;j<=min(m,i);j++)
  {//为了增强可读性，把状态转移方程分行了
   f[i][j][0]=min(f[i-1][j][0]+dist[c[i-1]][c[i]],
                  f[i-1][j][1]+k[i-1]*dist[d[i-1]][c[i]]
                  +(1-k[i-1])*dist[c[i-1]][c[i]]);
   if(j!=0)
    f[i][j][1]=min(f[i-1][j-1][0]+k[i]*dist[c[i-1]][d[i]]
                   +(1-k[i])*dist[c[i-1]][c[i]],
                   f[i-1][j-1][1]+k[i-1]*k[i]*dist[d[i-1]][d[i]]
                   +k[i-1]*(1-k[i])*dist[d[i-1]][c[i]]
                   +(1-k[i-1])*k[i]*dist[c[i-1]][d[i]]
                   +(1-k[i-1])*(1-k[i])*dist[c[i-1]][c[i]]);
  }
 double ans=INF;
 for(int i=0;i<=m;i++)
  ans=min(ans,min(f[n][i][0],f[n][i][1]));
 printf("%.2lf\n",ans);
 return 0;
}