CF 553E Kyoya and Train

• \(n\le 55\) 个点， \(m \le 100\) 条边的有向图，每条边有代价 \(c\)，且花费的时间为 \(1...t\) 的概率是给定的，若从 \(1\) 到 \(n\) 的总时间超过了 \(t\)，则还需付出 \(x\) 的代价，求出决策最优时的期望代价。

考虑 \(dp\)，设 \(f_{u,i}\) 为当前在 \(u\)，时间为 \(i\)，最少还需要付出代价的期望。

\(i > t\) 时，\(f_{u, i} = d_{i, n} + x\)，且 \(i\le t, f_{n,i} = 0\)。

考虑每条边对 \(f\) 的贡献，发现把 \(p\) 翻转以后是卷积的形式，所以可以分治 \(FFT\) 优化这个过程。

#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = (a); i <= (b); i++)
#define per(i, a, b) for (int i = (a); i >= (b); i--)
#define fi first
#define se second
typedef long long LL;
typedef pair <int, int> P;
const int inf = 0x3f3f3f3f, mod = 1e9 + 7, N = 4e4 + 5;
template <typename T>
inline void rd_(T &x) {
	x = 0; int f = 1;
	char ch = getchar();
	while (ch > ‘9‘ || ch < ‘0‘) { if (ch == ‘-‘) f = -1; ch = getchar(); }
	while (ch >= ‘0‘ && ch <= ‘9‘) x = x*10 + ch - ‘0‘, ch = getchar();
	x *= f;
}

struct C {
	double x, y;
	C (double a = 0, double b = 0) {
		x = a, y = b;
	}
} A[N], B[N];
C operator + (C a, C b) { return C(a.x + b.x, a.y + b.y); }
C operator - (C a, C b) { return C(a.x - b.x, a.y - b.y); }
C operator * (C a, C b) { return C(a.x*b.x - a.y*b.y, a.x*b.y + a.y*b.x); }

int n, m, t, x, d[55][55], a[105], b[105], c[105], len, cnt, rev[N];
double p[101][N], f[55][N], g[105][N], Pi = acos(-1);

void fft_(C *a, int f) {
	rep (i, 0, len - 1) if (i < rev[i]) swap(a[i], a[rev[i]]);
	for (int s = 2; s <= len; s <<= 1) {
		C wn(cos(2*Pi/s), f*sin(2*Pi/s));
		for (int j = 0; j < len; j += s) {
			C w(1, 0);
			for (int k = 0; k < s/2; k++, w = w*wn) {
				C u = a[j + k], v = a[j + k + s/2]*w;
				a[j + k] = u + v, a[j + k + s/2] = u - v;
			}
		}
	}
	if (f == -1)
		rep (i, 0, len - 1) a[i].x /= len;
}

void calc_(int x, int l, int r) {
	int mid = (l + r)>>1;
	for (len = 1, cnt = 0; len <= r - mid - 1 + r - l; len <<= 1) cnt++;
	rep (i, 0, len - 1) rev[i] = (rev[i>>1]>>1) + ((i&1)<<cnt - 1), A[i] = B[i] = (C) {0, 0};
	rep (i, 0, r - l - 1) A[i].x = p[x][i + 1];
	per (i, r, mid + 1) B[r - i].x = f[b[x]][i];
	fft_(A, 1), fft_(B, 1);
	rep (i, 0, len - 1) A[i] = A[i]*B[i];
	fft_(A, -1);
	rep (i, l, mid) g[x][i] += A[r - i - 1].x;
}

void solve_(int l, int r) {
	if (l >= t) return;
	if (l == r) {
		rep (i, 1, n - 1) f[i][l] = inf;
		rep (i, 1, m) f[a[i]][l] = min(f[a[i]][l], g[i][l] + c[i]);
		return; 
	}
	int mid = (l + r)>>1;
	solve_(mid + 1, r);
	rep (i, 1, m) 
		calc_(i, l, r);
	solve_(l, mid);
}

int main() {
	rd_(n), rd_(m), rd_(t), rd_(x);
	memset(d, 0x3f, sizeof(d));
	rep (i, 1, n) d[i][i] = 0;
	rep (i, 1, m) {
		rd_(a[i]), rd_(b[i]), rd_(c[i]);
		rep (j, 1, t) rd_(p[i][j]), p[i][j] /= 100000.0;
		d[a[i]][b[i]] = min(d[a[i]][b[i]], c[i]);
 	}
 	rep (k, 1, n) rep (i, 1, n) rep (j, 1, n) d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
 	rep (i, 0, 2*t - 1) f[n][i] = (i > t)*x;
 	rep (i, 1, n - 1) rep (j, t, 2*t - 1) f[i][j] = d[i][n] + x;
 	solve_(0, 2*t - 1);
 	return printf("%.7f\n", f[1][0]), 0;
}

CF 553E Kyoya and Train

原文：https://www.cnblogs.com/ympc2005/p/14303405.html