斯德哥尔摩 的博客

斯德哥尔摩 的博客

P1850 换教室

posted on 2018-10-29 21:12:39 | under 刷题 |

P1850 换教室

首先,$Floyd$跑出每对教室之间的最短路。

由于$V\leq 300$,所以可行。

但是然后呢?

这种概率期望题绝对和$DP$逃不了关系。。。

于是开始想$DP$。

本蒟蒻一开始设$dp[i][j]$表示到了第$i$个时间段,申请了$j$门课程到另外的教室,所能达到的期望值。

但是推转移方程时发现要$O(n^3)$转移。。。

因为我们并不知道前面选了哪$j$门课程。。。

具体来说,我们不知道上一次选了哪门课程,只能暴力枚举。。。

于是改一下:

设$dp[i][j][0/1]$表示到了第$i$个时间段,申请了$j$门课程到另外的教室,$0/1$表示第$i$门课程有没有申请到另外的教室,所能达到的期望值。

然后就可以推转移方程了。

我用$path[i][j]$表示$i,j$两个教室之间的最短路。

先考虑不到另外的教室:

如果$i-1$时没有换教室,那么$i-1$到$i$只有一种情况就是都不换教室;

如果$i-1$时换了教室,那么就有两种情况:$i-1$换成功了,或者没换成功。

所以就是对应的路径长乘上对应的概率。

方程:

$$dp[i][j][0]=\min\left\{\begin{array}{}dp[i-1][j][0]+path[c_{i-1}][c_i],\\\\dp[i-1][j][1]+path[c_{i-1}][c_i]\times(1-k_{i-1})\\+path[d_{i-1}][c_i]\times k_{i-1}\end{array}\right.$$

再考虑申请到另外的教室:

显然对于$i-1$可以是$k==0\|k==1$。

对于$k==0$有两种情况,$k==1$有四种情况,就不一一分析了。

列成方程如下:

$$dp[i][j][1]=\min\left\{\begin{array}{}dp[i-1][j-1][0]+path[c_{i-1}][c_i]\times(1-k_i)\\+path[c_{i-1}][d_i]\times k_i\\\\dp[i-1][j-1][1]+path[d_{i-1}][d_i]\times k_{i-1}\times k_i\\+path[d_{i-1}][c_i]\times k_{i-1}\times(1-k_i)\\+path[c_{i-1}][d_i]\times(1-k_{i-1})\times k_i\\+path[c_{i-1}][c_i]\times(1-k_{i-1})\times(1-k_i)\end{array}\right.$$

最终答案显然是:$$\min\left\{\begin{array}{}dp[n][i][0]\\dp[n][i][1]\end{array}\right.,i\in[0,m]$$

附代码:

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 2010
#define MAXM 310
#define MAX 999999999
using namespace std;
int n,m,V,E,c=1;
int path[MAXM][MAXM];
double ans=(1LL<<62),dp[MAXN][MAXN][2];
struct Time{
    int c,d;
    double k;
}a[MAXN];
inline int read(){
    int date=0,w=1;char c=0;
    while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
    while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
    return date*w;
}
void floyd(){
    for(int k=1;k<=V;k++)
    for(int i=1;i<=V;i++)
    for(int j=1;j<=V;j++)
    path[i][j]=min(path[i][j],path[i][k]+path[k][j]);
}
void work(){
    int x1,x2,y1,y2;
    double w1,w2,w3,w4;
    dp[1][0][0]=dp[1][1][1]=0;
    for(int i=2;i<=n;i++){
        x1=a[i-1].c;y1=a[i-1].d;x2=a[i].c;y2=a[i].d;

        w1=path[x1][x2];w2=path[x1][y2];w3=path[y1][x2];w4=path[y1][y2];

        dp[i][0][0]=dp[i-1][0][0]+w1;
        for(int j=1;j<=i&&j<=m;j++){

            dp[i][j][0]=min(dp[i][j][0],
                            min(dp[i-1][j][0]+w1,
                                dp[i-1][j][1]+w1*(1.00-a[i-1].k)+w3*a[i-1].k
                            )
                        );

            dp[i][j][1]=min(dp[i][j][1],
                            min(dp[i-1][j-1][0]+w1*(1.00-a[i].k)+w2*a[i].k,
                                dp[i-1][j-1][1]+
                                    w4*a[i-1].k*a[i].k+w3*a[i-1].k*(1.00-a[i].k)+
                                    w2*(1.00-a[i-1].k)*a[i].k+w1*(1.00-a[i-1].k)*(1.00-a[i].k)
                            )
                        );
        }
    }
    for(int i=0;i<=m;i++)ans=min(ans,min(dp[n][i][0],dp[n][i][1]));
    printf("%.2lf\n",ans);
}
void init(){
    int u,v,w;
    n=read();m=read();V=read();E=read();
    for(int i=1;i<=n;i++)a[i].c=read();
    for(int i=1;i<=n;i++)a[i].d=read();
    for(int i=1;i<=n;i++)scanf("%lf",&a[i].k);
    for(int i=1;i<=V;i++)
    for(int j=1;j<=V;j++)
    path[i][j]=(i==j?0:MAX);
    for(int i=1;i<=E;i++){
        u=read();v=read();w=read();
        if(u==v)continue;
        path[u][v]=path[v][u]=min(path[u][v],w);
    }
    floyd();
    memset(dp,127,sizeof(dp));
}
int main(){
    init();
    work();
    return 0;
}