P1850 [NOIP 2016 提高组] 换教室——最短路+期望dp

li_cat · 2025-05-26 22:13:12 · 个人记录

虽然是课上的例题还是觉得有必要记一下
因为最开始看到的时候我产生的思路太奇怪了

思路

首先第一眼看 n 很小，可以直接floyd求最短路

然后到了dp的环节

我的初见思路非常奇怪

噢节点要一维……哦对时间也要一维……使用次数要一维……那这样的话转移的过程中还要一维记录到这个节点有没有用……

肉眼可见走歪了，但是还是可以掰回来的

可以发现，节点和时间那一维是可以被压掉的，因为对于一个时间 i 只有可能在 c_i 和 d_i 两个位置

这样的话转移就比较舒服了

这个时候一个很重要的点就来了
要清楚什么是能自己决定的决策，什么是被概率影响的结果

对于决策，你是可以挑选的(体现在转移过程中的 \min/\max )
但是被概率限制的结果不可以选择，也就是说体现在期望上

然后转移过程并不复杂有点复杂

繁琐的转移

首先是这个节点不用申请的情况

• 一个是从上一个没有申请的课转移过来
• 一个是从上一个申请过的课转移过来，其中有两个我决定不了的情况
  • 申请成功，从d的点过来
  • 申请失败，从c的点过来（注意这个体现在期望里）

然后是这个节点一定申请的情况

• 一个是从上一个没有申请的课转移过来
  • 成功，从c到d
  • 失败，从c到c，也是体现在期望里
• 一个是从上一个申请过的课转移过来
  • 上一个申请成功，从d的点过来
  • 这次成功，到d
  • 这次失败，到c
  • 上一个申请失败，从c的点过来
  • 这次成功，到d
  • 这次失败，到c

思路清晰但是过程繁琐

最后注意，起始状态中第一节课是可以申请换教室的

AC Code:

#include <bits/stdc++.h>
#define db double
using namespace std;

const int MAXV=305;
const int MAXN=3005;
const int inf=0x3f3f3f3f;

int dis[MAXV][MAXV],c[MAXN],d[MAXN];
db dp[MAXN][MAXN][2],p[MAXN];
int n,m,v,e;

void floyd(){
    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]);
}//

void work(){
    scanf("%d%d%d%d",&n,&m,&v,&e);
    memset(dis,inf,sizeof(dis));
    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",&p[i]);
    for(int i=1,x,y,w;i<=e;++i){
        scanf("%d%d%d",&x,&y,&w);
        dis[x][y]=dis[y][x]=min(dis[x][y],w);
    }//
    for(int i=1;i<=v;++i)
        dis[i][i]=0;

    floyd();

//  printf("\n");
//  for(int i=1;i<=v;++i){
//      for(int j=1;j<=v;++j)
//          printf("%d ",dis[i][j]);
//      printf("\n");
//  }
    for(int i=1;i<=n;++i)
        for(int j=0;j<=m;++j)
            for(int k=0;k<=1;++k)
                dp[i][j][k]=1e9;

    dp[1][0][0]=0;
    dp[1][1][1]=0;
    for(int i=2;i<=n;++i){
        //j=0
        dp[i][0][0]=dp[i-1][0][0]+dis[c[i-1]][c[i]];
        dp[i][0][1]=1e9;
        for(int j=1;j<=m;++j){
            dp[i][j][0]=min(dp[i-1][j][0]+dis[c[i-1]][c[i]],
            dp[i-1][j][1]+(dis[d[i-1]][c[i]]*p[i-1]+dis[c[i-1]][c[i]]*(1-p[i-1])) );

            dp[i][j][1]=min(
            dp[i-1][j-1][0]+(dis[c[i-1]][d[i]]*p[i]+dis[c[i-1]][c[i]]*(1-p[i])),
            dp[i-1][j-1][1]+( (dis[d[i-1]][d[i]]*p[i-1]+dis[c[i-1]][d[i]]*(1-p[i-1]))*p[i]+ (dis[d[i-1]][c[i]]*p[i-1]+dis[c[i-1]][c[i]]*(1-p[i-1]))*(1-p[i])));
        }
    }

    db res=1e9;

    for(int i=0;i<=m;++i)
        res=min(res,min(dp[n][i][1],dp[n][i][0]));

    printf("%.02lf",res);
}//

int main(){
    work();
    return 0;
}