Kyoya and Train

题目描述

Kyoya Ootori wants to take the train to get to school. There are $n$ train stations and $m$ one-way train lines going between various stations. Kyoya is currently at train station $1$, and the school is at station $n$. To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $t$ time units, he will have to pay a fine of $x$.

Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $i$ has ticket cost $c_i$, and a probability distribution $p_{i, k}$ which denotes the probability that this train will take $k$ time units for all $1 \le k \le t$. Amounts of time that each of the trains used by Kyouya takes are mutually independent random values (moreover, if Kyoya travels along the same train more than once, it is possible for the train to take different amounts of time and those amounts are also independent one from another).

Kyoya wants to get to school by spending the least amount of money in expectation (for the ticket price plus possible fine for being late). Of course, Kyoya has an optimal plan for how to get to school, and every time he arrives at a train station, he may recalculate his plan based on how much time he has remaining. What is the expected cost that Kyoya will pay to get to school if he moves optimally?

题意概述

有$n$座城市和$m$条铁路，第$i$条铁路从$a_i$号城市出发，到达$b_i$号城市，票价为$c_i$。某人要在$t$个单位时间内从$1$号城市到$n$号城市，如果超过时间就会被罚款$x$。已知每次搭乘第$i$条铁路有$p_{i, k}$的概率需要$k \ (1 \le k \le t)$个单位时间。求在采取最优策略的情况下总花费的期望。

数据范围：$2 \le n \le 50, \ 1 \le m \le 100, \ 1 \le t \le 20000, \ 0 \le x \le 10^6$。

算法分析

首先考虑最暴力的 DP。令$f_{i, j}$表示当前时刻为$j$，在最优策略下从$i$号城市到$n$号城市的总花费的期望。那么

$$
f_{i, j}=
\begin{cases}
\min(c_e+\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k} \mid e \in [1, m] \land a_e=i), & i \lt n \land j \le t \\
d_{i, n}+x , & i \lt n \land j \gt t \\
0, & i=n \land j \le t \\
x, & i=n \land j \gt t
\end{cases}
$$

第二部分中的$d_{i, n}$表示在只考虑铁路票价的情况下从$i$号城市到$n$号城市的最小花费（因为已经超时了，所以不如走总票价最少的路）。

这样做的复杂度是$O(mt^2)$的，需要对它进行优化。令

$$
S_{e, j}=\sum_{k=1}^t p_{e, k} \cdot f_{b_e, j+k}
$$

转移方程的第一部分变为

$$
f_{i, j}=\min(c_e+S_{e, j} \mid e \in [1, m] \land a_e=i)
$$

对于$S$，它类似于卷积，可以将其中一部分翻转后用 FFT 求值；对于$f$，可以用 CDQ 分治，统计较大的$j$对较小的$j$的贡献。

具体来说，假设我们要计算$l \le j \le r$的$f_{i, j}$，令$mid=\lfloor {l+r \over 2} \rfloor$，那么先计算$mid \lt j \le r$的$f_{i, j}$，用这些来更新$l \le j \le mid$的$S_{e, j}$（$m$条边分别用 FFT 更新，复杂度$O(m(r-l)\log (r-l))$），最后计算$l \le j \le mid$的$f_{i, j}$。当$l=r$时$f$可以直接由$S$得到。总复杂度降至$O(mt\log^2t)$。

实现时细节很多，要注意 DP 边界条件和 FFT 下标变换。

代码

/*
 * Your nature demands love and your happiness depends on it.
 */

#include <algorithm>
#include <cmath>
#include <cstdio>
#include <cstring>

static int const N = 55;
static int const M = 105;
static int const T = 100000;
static double const PI = acos(-1);
int rev[T];

class Point {
public:
  double x, y;
  Point(double _x = 0, double _y = 0) : x(_x), y(_y) {}
  std::pair<double, double> pair() {
    return std::make_pair(x, y);
  }
  friend Point operator+(Point const &a, Point const &b) {
    return Point(a.x + b.x, a.y + b.y);
  }
  friend Point operator-(Point const &a, Point const &b) {
    return Point(a.x - b.x, a.y - b.y);
  }
  friend Point operator*(Point const &a, Point const &b) {
    return Point(a.x * b.x - a.y * b.y, a.x * b.y + a.y * b.x);
  }
  Point operator/(double const &n) {
    return Point(x / n, y / n);
  }
} wn[T], A[T], B[T];

int init(int n) {
  int m = n, l = 0;
  for (n = 1; n <= m; n <<= 1, ++l)
    ;
  for (int i = 1; i < n; ++i)
    rev[i] = rev[i >> 1] >> 1 | (i & 1) << l - 1;
  for (int i = 0; i < n >> 1; ++i)
    wn[i] = Point(cos(2 * PI / n * i), sin(2 * PI / n * i));
  return n;
}

void fft(Point *a, int n, int inv = 0) {
  for (int i = 0; i < n; ++i)
    if (i < rev[i])
      std::swap(a[i], a[rev[i]]);
  for (int i = 1; i < n; i <<= 1)
    for (int j = 0; j < n; j += i << 1)
      for (int k = 0; k < i; ++k) {
        Point x = a[j + k], y = wn[n / (i << 1) * k] * a[j + k + i];
        a[j + k] = x + y, a[j + k + i] = x - y;
      }
  if (inv) {
    std::reverse(a + 1, a + n);
    for (int i = 0; i < n; ++i)
      a[i] = a[i] / n;
  }
}

int n, m, t, x, mp[N][N];
double p[M][T], s[M][T], f[N][T];
struct Line {
  int a, b, c;
} li[M];

void update(int l, int r) {
  int mid = l + r >> 1, len = init(r - l + r - mid - 2);
  for (int i = 1; i <= m; ++i) {
    for (int j = 0; j < len; ++j)
      A[j] = B[j] = 0;
    for (int j = mid + 1; j <= r; ++j)
      A[j - mid - 1] = f[li[i].b][r - j + mid + 1];
    for (int j = 1; j <= r - l; ++j)
      B[j - 1] = p[i][j];
    fft(A, len), fft(B, len);
    for (int j = 0; j < len; ++j)
      A[j] = A[j] * B[j];
    fft(A, len, 1);
    for (int j = l; j <= mid; ++j)
      s[i][j] += A[r - j - 1].x;
  }
}

void solve(int l, int r) {
  if (l == r) {
    for (int i = 1; i <= m; ++i)
      f[li[i].a][l] = std::min(f[li[i].a][l], s[i][l] + li[i].c);
    return;
  }
  int mid = l + r >> 1;
  solve(mid + 1, r), update(l, r), solve(l, mid);
}

int main() {
  scanf("%d%d%d%d", &n, &m, &t, &x);
  memset(mp, 0x3f, sizeof mp);
  for (int i = 1; i <= m; ++i) {
    scanf("%d%d%d", &li[i].a, &li[i].b, &li[i].c);
    mp[li[i].a][li[i].b] = std::min(mp[li[i].a][li[i].b], li[i].c);
    for (int j = 1; j <= t; ++j)
      scanf("%lf", &p[i][j]), p[i][j] /= 100000;
  }
  for (int i = 1; i <= n; ++i)
    for (int j = 1; j <= n; ++j)
      for (int k = 1; k <= n; ++k)
        mp[j][k] = std::min(mp[j][k], mp[j][i] + mp[i][k]);
  for (int i = 1; i <= n; ++i)
    for (int j = 0; j <= t << 1; ++j)
      if (i == n)
        if (j <= t)
          f[i][j] = 0;
        else
          f[i][j] = x;
      else
        if (j <= t)
          f[i][j] = 1e9;
        else
          f[i][j] = x + mp[i][n];
  update(0, t << 1), solve(0, t), printf("%.8lf\n", f[1][0]);
  return 0;
}