真的是好题啊，让我对凸包的理解增加了非常非常多...
DP
推完式子可以发现，当我们可以升级某一个游戏，我们之后每一轮肯定会升级 \(b_i \times p_i\) 最大的那个游戏，这样是最优的。
设 \(B = \max(b_i \times p_i)\)，可以列 DP：
设 \(f_i\) 表示还剩 \(i\) 轮，目前没有升级过的期望：
\[f_i = \displaystyle \max_{j=1}^{n}\{(1 - p_j) \times f_{i-1} + p_j \times (a_j + B(i - 1))\} \]
这样是 \(O(nt)\) 显然差的远呢。
斜率优化
试试斜率优化，先把 \(\max\) 去掉然后移项：
\(f_i = f_{i-1} - p_jf_{i-1} + p_ja_j + p_jB(i-1)\)
\[p_j(f_{i-1} - B(i-1)) + f_i - f_{i - 1} = p_ja_j \]
我们提前按 \(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} \times (1 - p_j) + (i - 1) \times p_jB + 1 \times p_ja_j $
\(\begin{bmatrix} f_i & i & 1 \end{bmatrix} \times \begin{bmatrix} 1 - p_j & 0 & 0 \\ p_jB & 1 & 0\\ p_ja_j& 1& 1 \end{bmatrix} = \begin{bmatrix} f_{i+1} & i+1 & 1 \end{bmatrix}\)
这样就可以矩阵快速幂 \(O(27\log)\) 跑一段了。
那么我们考虑把每一段作为决策的区间找到。
怎么找呢？
- 二分，每次二分一个右端点 \(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\n", res.w[0][0]);
return 0;
}
总结
这题让我学会了...
- 凸包上凸壳怎么维护
- 从决策来考虑区间转移，每一段快速算出（考虑快速幂、倍增等 log 算法），神奇的优化。