LuoguP1850 - [NOIP2016] 换教室

2017/10/30

这么水的题都要调好久,我…

题目

对于刚上大学的牛牛来说,他面临的第一个问题是如何根据实际情况申请合适的课程。

在可以选择的课程中,有 2n 节课程安排在 n 个时间段上。在第 i 个时间段上,两节 内容相同的课程同时在不同的地点进行,其中,牛牛预先被安排在教室 ci 上课,而另一 节课程在教室 di 进行。

在不提交任何申请的情况下,学生们需要按时间段的顺序依次完成所有的 n 节安排好的 课程。如果学生想更换第 i 节课程的教室,则需要提出申请。若申请通过,学生就可以 在第 i 个时间段去教室 di 上课,否则仍然在教室 ci 上课。

由于更换教室的需求太多,申请不一定能获得通过。通过计算,牛牛发现申请更换第 i 节 课程的教室时,申请被通过的概率是一个已知的实数 ki ,并且对于不同课程的申请,被通 过的概率是互相独立的。

学校规定,所有的申请只能在学期开始前一次性提交,并且每个人只能选择至多 m 节课程 进行申请。这意味着牛牛必须一次性决定是否申请更换每节课的教室,而不能根据某些课程 的申请结果来决定其他课程是否申请;牛牛可以申请自己最希望更换教室的 m 门课程,也 可以不用完这 m 个申请的机会,甚至可以一门课程都不申请。

因为不同的课程可能会被安排在不同的教室进行,所以牛牛需要利用课间时间从一间教室赶到 另一间教室。

牛牛所在的大学有 v 个教室,有 e 条道路。每条道路连接两间教室,并且是可以双向通 行的。由于道路的长度和拥堵程度不同,通过不同的道路耗费的体力可能会有所不同。 当第 i 节课结束后,牛牛就会从这节课的教室出发,选择一条耗费体力最少的路径前往下一 节课的教室。

现在牛牛想知道,申请哪几门课程可以使他因在教室间移动耗费的体力值的总和的期望值最小, 请你帮他求出这个最小值。

解法

先跑 Floyd 求教室间的最短路长度。

然后期望 dp,令

表示已经用 k 次换课机会,当前做到 i ,且 i 换 (j = 1) 或 不换 (j = 0) 的期望最短长度。

转移就很好写出来,但是很长。

代码

 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
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const int _inf = 0x3f3f3f3f;
const int SIZ = 6000;

int N, M, V, E;

int C[SIZ][2];
double K[SIZ];
int Mat[2000][2000];

void Floyd() {
    for(int k=1;k<=V;k++)
        for(int i=1;i<=V;i++)
            for(int j=1;j<=V;j++)
                Mat[i][j] = min(Mat[i][j], Mat[i][k] + Mat[k][j]);
}

int dist(int x, int y) {
    if(x == 0) return 0.0;
    else return Mat[x][y];
}

double F[SIZ][SIZ][2]; // [用几次][做到第几个][这个是否换] 的最小期望
void DP() {
    for(int k=0;k<=M;k++)
        for(int i=1;i<=N;i++)
            F[k][i][0] = F[k][i][1] = double(_inf);

    for(int i=1;i<=N;i++)
        F[0][i][0] = F[0][i-1][0] + dist(C[i-1][0], C[i][0]);

    for(int k=1;k<=M;k++) {
        for(int i=1;i<=N;i++) {
            double k0 = F[k][i-1][1] + dist(C[i-1][0], C[i][0]); // Fail
            double k1 = F[k][i-1][1] + dist(C[i-1][1], C[i][0]); // Succ
            F[k][i][0] =
                min(F[k][i-1][0] + dist(C[i-1][0], C[i][0]),
                   k0 * (1 - K[i-1]) + k1 * K[i-1]);
            
            double a0 = F[k-1][i-1][0] + dist(C[i-1][0], C[i][0]); // Fail
            double a1 = F[k-1][i-1][0] + dist(C[i-1][0], C[i][1]); // Succ
            double at = a0 * (1 - K[i]) + a1 * K[i];

            double b00 = F[k-1][i-1][1] + dist(C[i-1][0], C[i][0]);
            double b01 = F[k-1][i-1][1] + dist(C[i-1][0], C[i][1]);
            double b10 = F[k-1][i-1][1] + dist(C[i-1][1], C[i][0]);
            double b11 = F[k-1][i-1][1] + dist(C[i-1][1], C[i][1]);

            double bt = b00 * (1 - K[i-1]) * (1 - K[i]) +
                    b01 * (1 - K[i-1]) * (K[i]) +
                    b10 * (K[i-1]) * (1 - K[i]) +
                    b11 * (K[i-1]) * (K[i]);

//          printf("! %d %d %.2lf %.2lf\n", k, i, at, bt);

            F[k][i][1] = min(at, bt);
        }
    }
}

int main() {
    scanf("%d %d %d %d", &N, &M, &V, &E);
    for(int i=1;i<=N;i++) scanf("%d", &C[i][0]);
    for(int i=1;i<=N;i++) scanf("%d", &C[i][1]);

    for(int i=1;i<=N;i++) scanf("%lf", &K[i]);

    for(int i=1;i<=V;i++) for(int j=1;j<=V;j++) Mat[i][j] = _inf;
    for(int i=1;i<=V;i++) Mat[i][i] = 0;

    int u, v, w;
    for(int i=1;i<=E;i++) {
        scanf("%d %d %d", &u, &v, &w);
        Mat[u][v] = min(Mat[u][v], w);
        Mat[v][u] = Mat[u][v];
    }

    Floyd();

    DP();

    double ans = _inf;
    for(int i=0;i<=M;i++) ans = min(ans, min(F[i][N][0], F[i][N][1]));

    printf("%.2lf\n", ans);
}