M_sea

洛谷1850 换教室
Luogu算法期望DP。先用Floyd求出最短路。设$f[i] [j] [0]$表示前$i$个教室申请$j$次,这...
扫描右侧二维码阅读全文
16
2017/09

洛谷1850 换教室

Luogu

算法

期望DP。

先用Floyd求出最短路。

设$f[i] [j] [0]$表示前$i$个教室申请$j$次,这一次未通过的最小体力,$f[i] [j] [1]$表示前$i$个教室申请$j$次,这一次通过的最小体力。
$f[i] [j] [0]$的转移很容易:

$f[i][j][0]=min(\\f[i-1][j][0]+g[c[i-1]][c[i]],\\f[i-1][j][1]+g[c[i-1]][c[i]]*(1.0-k[i-1])+g[d[i-1]][c[i]]*k[i-1])$

但是$f[i] [j] [1]$需要考虑的东西就很多了。

$f[i][j][1]=min(\\f[i-1][j-1][0]+g[c[i-1]][c[i]]*(1.0-k[i])+g[c[i-1]][d[i]]*k[i],\\f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1.0-k[i-1])*(1.0-k[i])\\+g[d[i-1]][c[i]]*k[i-1]*(1.0-k[i])+\\g[c[i-1]][d[i]]*(1.0-k[i-1])*k[i]+g[d[i-1]][d[i]]*k[i-1]*k[i])$

解释一下,首先是min的前项这一块。它表示的是这一次没通过的期望体力加上通过的期望体力。
后面的类似,表示上一次未通过这一次未通过+上一次通过这一次未通过+上一次未通过这一次通过+上一次通过这一次通过的期望体力。

注意边界:$f[1] [0] [0]=f[1] [1] [1]=0$
一开始要全部初始化为$+\infty$。

答案就是所有$f[n] [i] [0]$与$f[n] [i] [1]$的最小值($1\leq i\leq m$)。

代码

#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#define re register
using namespace std;
int n,m,v,e;
int c[2010],d[2010]; //教室
double k[2010]; //概率
int g[310][310]; //输入图&最短路
double f[2010][2010][2]; //DP用
inline int read() //读入优化
{
    int X=0,w=1; char ch=getchar();
    while (ch<'0'||ch>'9') { if (ch=='-') w=-1; ch=getchar(); }
    while (ch>='0'&&ch<='9') X=(X<<3)+(X<<1)+ch-'0',ch=getchar();
    return X*w;
}
inline void Init() //输入&初始化
{
    n=read(); m=read(); v=read(); e=read(); 
    for (re int i=1;i<=n;i++) c[i]=read();
    for (re int i=1;i<=n;i++) d[i]=read();
    for (re int i=1;i<=n;i++) scanf("%lf",&k[i]); //输入
    for (re int i=0;i<=309;i++) //初始化,注意范围
        for (re int j=0;j<=309;j++)
        {
            if (i==j) g[i][j]=0;
            else g[i][j]=1000000000;
        }
    for (re int i=0;i<=2001;i++)//同上
        for (re int j=0;j<=2001;j++)
            f[i][j][0]=f[i][j][1]=1000000000;
    f[1][0][0]=f[1][1][1]=0; //DP边界
    int u,v,w;
    for (int i=1;i<=e;i++)  //输入图
    {
        u=read(); v=read(); w=read();
        if (u==v) continue; //自环
        if (w<g[u][v]) g[u][v]=w; //重边
        g[v][u]=g[u][v];
    }
}
inline void Floyd() //Floyd
{
    for (re int k=1;k<=v;k++)
        for (re int i=1;i<=v;i++)
            for (re int j=1;j<=v;j++)
                if (g[i][k]+g[k][j]<g[i][j])
                    g[i][j]=g[i][k]+g[k][j];
}
inline void DP() 
{
    for (re int i=2;i<=n;i++) //从2开始DP
    {
        f[i][0][0]=f[i-1][0][0]+g[c[i-1]][c[i]]; //算一下f[i][0][0],不讲
        for (int j=1;j<=min(i,m);j++) //从1到min(i,m),要取min否则会错
        {
            f[i][j][0]=min(f[i-1][j][0]+g[c[i-1]][c[i]],f[i-1][j][1]+g[c[i-1]][c[i]]*(1.0-k[i-1])+g[d[i-1]][c[i]]*k[i-1]); //计算f[i][j][0]
            f[i][j][1]=f[i-1][j-1][0]+g[c[i-1]][c[i]]*(1.0-k[i])+g[c[i-1]][d[i]]*k[i]; //f[i][j][1]的前面部分
            double t=f[i-1][j-1][1]+g[c[i-1]][c[i]]*(1.0-k[i-1])*(1.0-k[i]);
            t+=g[d[i-1]][c[i]]*k[i-1]*(1.0-k[i]);
            t+=g[c[i-1]][d[i]]*(1.0-k[i-1])*k[i];
            t+=g[d[i-1]][d[i]]*k[i-1]*k[i]; //后面部分,累加
            f[i][j][1]=min(f[i][j][1],t); //取min
        }
    }
}
int main()
{
    Init(); //输入&初始化
    Floyd(); //Floyd
    DP(); //DP
    double ans=f[n][0][0]; //ans一开始是不换教室的最小体力
    for (int i=1;i<=m;i++) ans=min(ans,min(f[n][i][0],f[n][i][1])); //更新ans
    printf("%.2lf\n",ans); //输出,保留两位小数
    return 0;
}
最后修改:2018 年 12 月 26 日 08 : 35 PM

发表评论