(luogu1850) 换教室 (NOIP2016 D1T3)

发表于 分类于 ，

去年的真题，经典 dp ## 题目描述:

略

思路:

floyd 求最短路 + 概率 dp

先用 floyd 求出每两个点间的最短距离

用 d (i,j,0/1) 表示在前 i 个时间段，换教室 j 次， 第 i 次换或不换的最小数学期望

答案为 min {d (n,j,0/1)}(0<=j<=m)

转移方程见代码

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int Mn(2005);
const int Mm(2005);
const int Mv(305);
void qr(int& x) //快速读入
{
    x=0; char c(getchar());
    while(c<'0' || c>'9')	c=getchar();
    while(c>='0'&&c<='9')
    {
        x=x*10+(c-'0');
        c=getchar();
    }
}
double f[Mn][Mm][2];
int dis[Mv][Mv];
int c[Mn],d[Mn];
double p[Mn];
int main()
{
    int n,m,e,v;
    cin >> n >> m >> v >> e;
    for(int i(1);i<=n;++i)
        qr(c[i]);
    for(int i(1);i<=n;++i)
        qr(d[i]);
    for(int i(1);i<=n;++i)
        scanf("%lf",p+i);
    memset(dis,0x3f,sizeof dis);
    for(int i(1);i<=v;++i)
        dis[i][i]=0;
    while(e--)
    {
        int x,y,z;
        qr(x),qr(y),qr(z);
        dis[x][y] = dis[y][x] = min(dis[x][y],z);
    }
    /*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]);
    m = min(n,m); //!!!m最多与n相等
    for(int i(1);i<=n;++i)
        for(int j(0);j<=m;++j)
            f[i][j][0] = f[i][j][1] = 1e15;
    f[1][0][0] = f[1][1][1] = 0;
    for(int i(2);i<=n;++i)
    {
        for(int j(0);j<=m && j<=i;++j) //j最多与i相等
        {
            f[i][j][0] = f[i-1][j][0] + dis[c[i-1]][c[i]]; //这次不换教室, 上一次也没换
            if(j>0)	f[i][j][0] = min(f[i][j][0],f[i-1][j][1] + (p[i-1]*dis[d[i-1]][c[i]]) + ((1.0-p[i-1])*dis[c[i-1]][c[i]])); //这次不换, 上次换了
            if(j>0)	f[i][j][1] = f[i-1][j-1][0] + (p[i]*dis[c[i-1]][d[i]]) + ((1.0-p[i])*dis[c[i-1]][c[i]]); //这次换了, 上次没换
            if(j>1)	f[i][j][1] = min(f[i][j][1],f[i-1][j-1][1]+(p[i-1]*p[i]*dis[d[i-1]][d[i]])+(p[i-1]*(1.0-p[i])*dis[d[i-1]][c[i]])+((1.0-p[i-1])*p[i]*dis[c[i-1]][d[i]])+((1.0-p[i-1])*(1.0-p[i])*dis[c[i-1]][c[i]])); //这次换了, 上次也换了
        }
    }
    double ans(1e15);
    for(int i(0);i<=m;++i)
    {
        ans = min(ans,f[n][i][0]);
        ans = min(ans,f[n][i][1]);
    }
    printf("%.2lf",ans);
    return 0;
}