真的是好题啊，让我对凸包的理解增加了非常非常多...
DP
推完式子可以发现，当我们可以升级某一个游戏，我们之后每一轮肯定会升级 (b_i imes p_i) 最大的那个游戏，这样是最优的。
设 (B = max(b_i imes p_i))，可以列 DP：
设 (f_i) 表示还剩 (i) 轮，目前没有升级过的期望：
这样是 (O(nt)) 显然差的远呢。
斜率优化
试试斜率优化，先把 (max) 去掉然后移项：
(f_i = f_{i-1} - p_jf_{i-1} + p_ja_j + p_jB(i-1))
我们提前按 (p) 排序，就做到了横坐标单调递增。
为了保持截距 (b) 最大，我们需要维护一个上凸包（即相邻两点之间斜率递减这样一个东西）。
设 (A_i = f_{i - 1} - Bi)，尝试证明 (A_i) 不增。
(A_i - A_{i - 1} = f_{i - 1} - f_{i - 2} - B(i-1) + B(i - 2) = f_{i - 1} - f_{i - 2} - B)。
显然两轮的差收益最大是 (B)，所以 (A_i - A_{i-1} le 0)，证毕。
这样斜率 (k) 是递减，横坐标是递增了。即每次我们要找到在凸包上 (k(i - 1, i) > k > k(i, i + 1)) 的位置，类似双指针的弹出方式，可以 (O(t)) 了。
奇怪的优化增加了
复杂度还是 8 行啊。
满足这样的斜率优化肯定满足决策单调性，考虑斜率优化的过程就可以。
这样的话，考虑每一段，都是相同的 (j)，那么
$f_i = f_{i - 1} imes (1 - p_j) + (i - 1) imes p_jB + 1 imes p_ja_j $
(egin{bmatrix} f_i & i & 1 end{bmatrix} imes egin{bmatrix} 1 - p_j & 0 & 0 \ p_jB & 1 & 0\ p_ja_j& 1& 1 end{bmatrix} = egin{bmatrix} f_{i+1} & i+1 & 1 end{bmatrix})
这样就可以矩阵快速幂 (O(27log)) 跑一段了。
那么我们考虑把每一段作为决策的区间找到。
怎么找呢？
- 二分，每次二分一个右端点 (r)，如何判定合法呢，看 (r) 的转移，如果 (r) 的转移仍为当前的决策，那么整段肯定都是当前决策。((l, r - 1)) 作为 (i) 跑矩阵快速幂，把 (f[r - 1]) 转移到 (f[r]) 看看 (j) 和 (j + 1) 谁优，如果 (j) 更优那么右端点可以继续往右，但是这样每次 check 也要 (log)，总复杂度 (O(27 n log^2)) 有点悬。
- 倍增，类似于 AcWing 109. 天才ACM。先提前把矩阵的 (2^k) 预处理出来，这样从大到小开始倍增，如果能跳就跳就可以了（类似二分的思路），这样可以做到 (O(27 n log))
Code
垃圾精度毁我青春，我自闭了。
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define x(u) (g[u].p)
#define y(u) (g[u].p * g[u].a)
using namespace std;
typedef long long LL;
const double eps = 1e-14;
const int N = 100005, L = 34;
LL T;
int n, q[N], hh = 1, tt = 0;
double B;
struct Game{
int a, b;
double p;
bool operator < (const Game &y) const {
if (fabs(y.p - p) < eps) return a * p > y.a * y.p;
return p < y.p;
}
} g[N];
double inline K(int a, int b) {
return (y(b) - y(a)) / (x(b) - x(a));
}
struct Matrix{
int n, m;
double w[3][3];
Matrix operator * (const Matrix b) const {
Matrix c; c.n = n, c.m = b.m;
memset(c.w, 0, sizeof c.w);
for (int i = 0; i < n; i++)
for (int j = 0; j < b.m; j++)
for (int k = 0; k < m; k++)
c.w[i][j] += w[i][k] * b.w[k][j];
return c;
}
} res, A[L];
Matrix inline build(int j) {
Matrix c; memset(c.w, 0, sizeof c.w);
c.n = 3, c.m = 3;
c.w[0][0] = 1 - g[j].p, c.w[1][0] = g[j].p * B, c.w[2][0] = g[j].p * g[j].a;
c.w[1][1] = c.w[2][1] = c.w[2][2] = 1;
return c;
}
double inline get(double S, int j) {
return g[j].p * (g[j].a - S);
}
int main() {
scanf("%d%lld", &n, &T);
for (int i = 1; i <= n; i++) {
scanf("%d%d%lf", &g[i].a, &g[i].b, &g[i].p);
B = max(B, g[i].b * g[i].p);
}
sort(g + 1, g + 1 + n);
for (int i = 1; i <= n; i++) {
if (i > 1 && fabs(g[i].p - g[i - 1].p) < eps) continue;
while (hh < tt && K(q[tt - 1], q[tt]) <= K(q[tt], i)) tt--;
q[++tt] = i;
}
res.n = 1, res.m = 3, res.w[0][2] = 1;
LL x = 0; double k = 0;
while (x != T) {
while (hh < tt && get(k, q[hh]) < get(k, q[hh + 1])) hh++;
A[0] = build(q[hh]);
for (int i = 1; i < L; i++) A[i] = A[i - 1] * A[i - 1];
for (int i = L - 1; ~i; i--) {
if (x + (1ll << i) < T) {
Matrix C = res * A[i];
double nK = C.w[0][0] - B * C.w[0][1];
if (hh == tt || get(nK, q[hh]) > get(nK, q[hh + 1]))
res = C, x += 1ll << i;
}
}
res = res * A[0], k = res.w[0][0] - B * res.w[0][1], ++x;
}
printf("%.16f
", res.w[0][0]);
return 0;
}
总结
这题让我学会了...
- 凸包上凸壳怎么维护
- 从决策来考虑区间转移，每一段快速算出（考虑快速幂、倍增等 log 算法），神奇的优化。