NOIp 2016 选课 (DP)

发表于 更新于 分类于

Problem

题目太长不复制粘贴了

Solution

经典的期望DP, 当作训练吧。

\(dp[i][j][0 / 1]\)表示前\(i\)门课使用\(j\)次申请换课机会, 本次选(\(1\))/不选(\(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
#include <algorithm>
#include <cstdio>
#include <cstring>
int n, m, v, e;
int c[2010], d[2010];
double k[2010];
double adj[310][310];
double dp[2010][2010][2], ans(999999999.999999);
int main(int argc, char const *argv[]) {
  // Input
  scanf("%d %d %d %d", &n, &m, &v, &e);
  for (register int i(1); i <= n; ++i) {
    scanf("%d", &c[i]);
  }
  for (register int i(1); i <= n; ++i) {
    scanf("%d", &d[i]);
  }
  for (register int i(1); i <= n; ++i) {
    scanf("%lf", &k[i]);
  }
  memset(adj, 0x43, sizeof(adj));
  {
    register double c;
    for (register int i(1), a, b; i <= e; ++i) {
      scanf("%d %d %lf", &a, &b, &c);
      adj[a][b] = adj[b][a] = std::min(adj[a][b], c);
    }
  }
  // Run Floyd-Warshall algorithm to get the lengths of shortest paths between
  // each pair of classrooms.
  for (register int k(1); k <= v; ++k) {
    adj[k][k] = adj[k][0] = adj[0][k] = 0;
    for (register int i(1); i <= v; ++i) {
      for (register int j(1); j <= v; ++j) {
        adj[i][j] = adj[j][i] = std::min(adj[i][j], adj[i][k] + adj[k][j]);
      }
    }
  }
  // Run Dynamic programming to get the answer.
  memset(dp, 0x43, sizeof(dp));
  dp[1][0][0] = dp[1][1][1] = 0.000000;
  for (register int i(2); i <= n; ++i) {
    for (register int j(0); j <= m && j <= i; ++j) {
      // Not apply this time
      dp[i][j][0] = std::min(
          // Didn't apply for exchange before the previous class
          dp[i - 1][j][0] + adj[c[i - 1]][c[i]],
          // Applied last time
          dp[i - 1][j][1] +
              // Failed last time
              (1.000000 - k[i - 1]) * adj[c[i - 1]][c[i]] +
              // Succeeded last time
              k[i - 1] * adj[d[i - 1]][c[i]]);
      // Apply this time
      if (j >= 1) {
        dp[i][j][1] = std::min(
            // Didn't apply for exchange before the previous class
            dp[i - 1][j - 1][0] +
                // Failed this time
                (1.000000 - k[i]) * adj[c[i - 1]][c[i]] +
                // Succeeded this time
                k[i] * adj[c[i - 1]][d[i]],
            // Applied last time
            dp[i - 1][j - 1][1] +
                // Failed both last and this time
                (1.000000 - k[i - 1]) * (1.000000 - k[i]) *
                    adj[c[i - 1]][c[i]] +
                // Succeeded last time and failed this time
                k[i - 1] * (1.000000 - k[i]) * adj[d[i - 1]][c[i]] +
                // Failed last time and succeeded this time
                (1.000000 - k[i - 1]) * k[i] * adj[c[i - 1]][d[i]] +
                // Succeeded both last and this time
                k[i - 1] * k[i] * adj[d[i - 1]][d[i]]);
      }
    }
  }
  for (register int i(0); i <= m; ++i) {
    ans = std::min(ans, std::min(dp[n][i][0], dp[n][i][1]));
  // Output
  printf("%.2lf\n", ans);
  return 0;
}