Codeforces

Luogu

分析

显然我们会在刷出一次升级机会后升级 $b_i\times p_i$ 最大的那个游戏,然后在接下来的时间内一直玩它。为了方便设 $M=\max\left\{b_i\times p_i\right\}$。

考虑 DP。设 $dp_i$ 表示还剩 $i$ 秒且还没有得到过升级机会的最大期望收益,枚举每个游戏可以得到转移

$$ dp_i=\max_j\left\{(1-p_j)dp_{i-1}+p_j(a_j+(i-1)M\right\} $$

拆开得到

$$ dp_i=\max_j\left\{-p_j[dp_{i-1}-(i-1)M]+p_ja_j\right\}+dp_{i-1} $$

设 $S_i=dp_i-iM$,上式改写为

$$ dp_i=\max_j\left\{-S_{i-1}p_j+p_ja_j\right\}+dp_{i-1} $$

可以看出是直线的形式,因此可以斜率优化,维护所有 $(p_i,p_ia_i)$ 的上凸壳即可。直接在凸壳上二分即可做到 $\mathcal{O}(t\log n)$。

可以发现 $S_i$ 是单调不升的,因为 $S_i-S_{i-1}=dp_i-dp_{i-1}-M$,而显然 $dp_i-dp_{i-1}\leq M$(一秒内的期望收益显然不会增加超过 $M$),所以 $S_i-S_{i-1}\leq 0$ 即 $S_i\leq S_{i-1}$。这样子可以做到 $\mathcal{O}(t)$。

因为 $t$ 比较大,而决策点只有 $\mathcal{O}(n)$ 个,因此会有许多地方的转移完全相同,可以用矩阵快速幂优化:

$$ \begin{bmatrix}dp_i&i&1\end{bmatrix}\times\begin{bmatrix}1-p_j&0&0\\p_jM&1&0\\p_ja_j&1&1\end{bmatrix}=\begin{bmatrix}dp_{i+1}&i+1&1\end{bmatrix} $$

于是只要快速找到决策点改变的位置即可。一个想法是二分后矩阵快速幂,判断对应位置的最优决策是不是当前决策点即可,然而是 $\mathcal{O}(27 n\log^2 t)$ 的,可能过不了。事实上预处理出矩阵的 $2^i$ 次幂并将二分改成倍增即可,这样就是 $\mathcal{O}(27 n\log t)$ 的了。

具体实现可以参考代码。

代码

// ====================================
//   author: M_sea
//   website: https://m-sea-blog.com/
// ====================================
#include <bits/stdc++.h>
#define file(x) freopen(#x".in","r",stdin); freopen(#x".out","w",stdout)
using namespace std;
typedef long long ll;

ll read() {
    ll X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=100000+10;
const double eps=1e-12;

int n; ll T; double M;
struct Game { int a,b; double p; } g[N];
bool operator <(Game a,Game b) { return a.p<b.p; }

double X(int i) { return g[i].p; }
double Y(int i) { return g[i].p*g[i].a; }
double slope(int i,int j) {
    if (fabs(X(i)-X(j))<eps) return Y(i)<Y(j)?1e50:-1e50;
    else return (Y(j)-Y(i))/(X(j)-X(i));
}
int q[N],h,t;

struct Matrix {
    double s[4][4];
    Matrix() { memset(s,0,sizeof(s)); }
    double* operator [](int i) { return s[i]; }
} F,pw[34];
Matrix operator *(Matrix a,Matrix b) {
    Matrix c;
    for (int k=0;k<3;++k)
        for (int i=0;i<3;++i)
            for (int j=0;j<3;++j)
                c[i][j]+=a[i][k]*b[k][j];
    return c;
}

int main() {
    n=read(),T=read();
    for (int i=1;i<=n;++i) {
        g[i].a=read(),g[i].b=read(),scanf("%lf",&g[i].p);
        M=max(M,g[i].b*g[i].p);
    }
    sort(g+1,g+n+1); h=1,t=0;
    for (int i=1;i<=n;++i) {
        while (h<t&&slope(q[t-1],q[t])<slope(q[t],i)+eps) --t;
        q[++t]=i;
    }
    F[0][2]=1;
    for (ll i=0;i!=T;) {
        while (h<t&&slope(q[h],q[h+1])+eps>F[0][0]-i*M) ++h;
        pw[0][0][0]=1-g[q[h]].p,pw[0][1][0]=g[q[h]].p*M,pw[0][1][1]=1;
        pw[0][2][0]=g[q[h]].p*g[q[h]].a,pw[0][2][1]=pw[0][2][2]=1;
        for (int j=1;j<=33;++j) pw[j]=pw[j-1]*pw[j-1];
        for (int j=33;~j;--j) {
            if (i+(1ll<<j)>=T) continue;
            Matrix G=F*pw[j];
            if (h==t||slope(q[h],q[h+1])<G[0][0]-(i+(1ll<<j))*M)
                i+=1ll<<j,F=G;
        }
        ++i,F=F*pw[0];
    }
    printf("%.7lf\n",F[0][0]);
    return 0;
}
最后修改:2020 年 08 月 10 日 11 : 43 AM