题解：CF1067D Computer Game

· · 题解

Computer Game

可以发现赢下一局后，会选择升级后期望收益 p\times b 最高的一种游戏玩到结束位置，记 (p\times b)_{\operatorname{max}} 为 V 。接下来考虑升级前的策略，由于不能找出直观的贪心策略，那就使用动态规划。设 f_t 表示游戏还剩 t 秒且在此之前没有赢过的期望收益最大值。可以列出转移方程：

f_t=\max_{i=1}^n\{p_i(a_i+(t-1)V)+f_{t-1}(1-p_i)\}

这样直接转移是 O(nt) 的，因此要优化转移。

首先把常量扔外面，再按照 i, t 整理式子：

f_t=\max_{i=1}^n\{p_i((t-1)V-f_{t-1})+p_ia_i)\}+f_{t-1}

由于转移的时候 t-1, f_{t-1} 是已知的，在一步转移中可以视为常量。而 V 也是已知常量，所以 (t-1)V-f_{t-1} 在一步转移中也可以视为常量。关于 i 的变量 p_i, p_ia_i，与转移的量相乘与相加，这种形式可以用使用斜率优化。还有不懂斜率优化的同学可以看这里。

然后显然有 f_t-f_{t-1}\leq V，所以 (t-1)V-f_{t-1}\leq tV-f_t，即式子中的 (t-1)V-f_{t-1} 是递增的，因此可以用单指针来维护最优解在凸包上的位置，即转移是 O(1) 的。

此时的复杂度就变成了 O(n+t)。

然后由于 (t-1)V-f_{t-1} 递增，所以游戏 i 作为最优解的时刻一定是一个区间，则对于每一段连续的区间，可以使用矩阵加速转移。即：

\begin{bmatrix}f_t&t&1\end{bmatrix}\times\begin{bmatrix}1-p_i&0&0\\p_iv&1&0\\p_ia_i&1&1\end{bmatrix}=\begin{bmatrix}f_{t+1}&t+1&1\end{bmatrix}

然后使用矩阵倍增，就可以在 O(\log t) 的时间内转移一段连续的区间了。总时间复杂度 O(n\log t)。

Code

#include <iostream>
#include <algorithm>
#include <string.h>
#include <iomanip>
#include <bitset>
#include <math.h>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define fst first
#define scd second
#define db double
#define ll long long
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector <int>
#define pii pair <int, int>
#define sz(x) ((int)x.size())
#define ms(f, x) memset(f, x, sizeof(f))
#define L(i, j, k) for (int i=(j); i<=(k); ++i)
#define R(i, j, k) for (int i=(j); i>=(k); --i)
#define ACN(i, H_u) for (int i=H_u; i; i=E[i].nxt)
using namespace std;
template <typename INT> void rd(INT &res) {
    res=0; bool f=false; char ch=getchar();
    while (ch<'0'||ch>'9') f|=ch=='-', ch=getchar();
    while (ch>='0'&&ch<='9') res=(res<<1)+(res<<3)+(ch^48), ch=getchar();
    res=(f?-res:res);
}
template <typename INT, typename...Args>
void rd(INT &x, Args &...y) { rd(x), rd(y...); }
//dfs
const int maxn=1e5;
const int N=maxn+10;
int n, stk[N], top; ll tv; db V;
//wmr
struct node {
    db x, y;
    bool operator < (const node &k) const { return x<k.x; }
} g[N];
struct matrix {
    db f[3][3];
    matrix() { L(i, 0, 2) L(j, 0, 2) f[i][j]=0; }
    void unit() { f[0][0]=f[1][1]=f[2][2]=1; }
} bin[40];
matrix operator * (const matrix &x, const matrix &y) {
    matrix z;
    L(k, 0, 2) L(i, 0, 2) L(j, 0, 2) z.f[i][j]+=x.f[i][k]*y.f[k][j];
    return z;
}
// db slope(int i, int j) { return (g[j].y-g[i].y)/(g[j].x-g[i].x); }
//incra

//lottle
signed main() {
//  ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    freopen("CF1067D.in", "r", stdin);
    freopen("CF1067D.out", "w", stdout);
    rd(n, tv);
    L(i, 1, n) {
        int a, b; db p;
        rd(a, b); scanf("%lf", &p);
        V=max(V, p*b); g[i].x=p, g[i].y=p*a;
    }
    sort(g+1, g+n+1);
    L(i, 1, n) {
        // while (top>1&&slope(i, stk[top])>=slope(stk[top], stk[top-1])) --top;
        while (top>1&&(g[i].y-g[stk[top]].y)*(g[stk[top]].x-g[stk[top-1]].x)>=(g[stk[top]].y-g[stk[top-1]].y)*(g[i].x-g[stk[top]].x)) --top;
        stk[++top]=i;
    }
    matrix res; res.f[0][2]=1; ll t=0;
    L(i, 1, top) {
        db val=t*V-res.f[0][0];
        // while (i<top&&-val<=slope(stk[i], stk[i+1])) ++i;
        while (i<top&&g[stk[i+1]].y-g[stk[i]].y+val*(g[stk[i+1]].x-g[stk[i]].x)>=0) ++i;
        bin[0].f[0][0]=1-g[stk[i]].x, bin[0].f[1][0]=g[stk[i]].x*V, bin[0].f[2][0]=g[stk[i]].y, bin[0].f[1][1]=bin[0].f[2][1]=bin[0].f[2][2]=1;
        int uj=__lg(tv-t);
        L(j, 1, uj) bin[j]=bin[j-1]*bin[j-1];
        R(j, uj, 0) if (t+(1ll<<j)<tv) {
            matrix tmp=res*bin[j]; val=(t+(1ll<<j))*V-tmp.f[0][0];
            // if (i==top||-val>=slope(stk[i], stk[i+1])) res=tmp, t+=(1ll<<j);
            if (i==top||g[stk[i+1]].y-g[stk[i]].y+val*(g[stk[i+1]].x-g[stk[i]].x)<=0) res=tmp, t+=(1ll<<j);
        }
        res=res*bin[0], ++t;
        if (t==tv) break;
    }
    printf("%.12lf\n", res.f[0][0]);
    return 0;
}
/*
input
4 1000000
2 3 0.00001
3 100 0.000004
5 1000 0.000001
8 3000 0.0000004
output
1082.0053569238542
*/