CF1067D - Computer Game

题目大意

给定 \(n\) 个操作，每个操作有1级和2级分别对应价值 \(a_i,b_i (a_i<b_i)\) ，初始每个操作为 \(1\) 级

每次操作 \(i\) ，有 \(p_i\) 概率操作成功，这会获得价值，并且获得一次升级的机会

求 \(t\) 次操作的期望最大权值和

分析

容易发现，当你拿到一次升级后，一定就一直选择 \(\max\{p_i\cdot b_i\}\) 进行操作

并且每次期望获得这么多的权值，不妨设 \(m=\max\{p_i\cdot b_i\}\)

需要决策的是拿到这个权值之前，选择哪一个操作

设 \(dp_i\) 表示有 \(i\) 次操作机会时的期望答案，则得到 \(dp\) 转移式子

\(\displaystyle dp_i=\max_{j\leq n}\{ p_j((i-1)m+a_j)+(1-p_j)dp_{i-1} \}\)

考虑这是一个斜率优化的形式，我们做一下变形

\(dp_i=\max\{ p_j((i-1)m-dp_{i-1}) +dp_{i-1}+p_ja_j\}\)

可以看到斜率优化与 \((i-1)m-dp_{i-1}\) 有关，设 \(g_i=im-dp_{i}\)

则问题可以转化为求 \((g_t)_{\min}\)

转化之后得到 \(g_i\) 的转移式

\(\displaystyle g_{i}=\min_{j\leq n} \{g_{i-1} (1-p_j)+m-a_jp_j\}\)

容易发现这样的转移相较于 \(dp_i\) ，脱离了 \(im\) 的问题

不妨对于 \((1-p_j,m-a_jp_j)\) 建立凸包，则转移可以斜率优化

现在考虑 \(g_i\) 的单调性，根据定义式我们可以感性地理解 \(g_i\) 是递增的（因为 \(dp_i\) 增率不可能超过 \(m\) ）

（事实上我并不知道怎么根据转移式说明它是单调的）

既然是 \(g_i\) 是单调，那么转移在凸包上的位置也是单调的，因此可以直接在凸包上移动决策点

倍增|二分完成操作

复杂度为 \(O(n(\log n+\log t))\) 或 \(O(n(\log n+\log^2 t))\)

吐槽

Codeforces上写double ,long double真的磨人

还有一群疯子构造数据把两个点的 \(x_i,y_i\) 相差 \(10^{-9}\)

什么玩意儿，搞得我把 \(\text{eps}\) 开成 \(10^{-20}\)

const int N=1e5+10,INF=1e9+10;
const db eps=1e-20;

int n; ll k;
db m;
struct Node{
	db x,y;
	Node(db x=0,db y=0):x(x),y(y){}
	bool operator < (const Node __) const { return x<__.x-eps || (fabs(x-__.x)<eps && y>__.y); }
	Node operator - (const Node _) const { return Node(x-_.x,y-_.y); }
	db operator ^ (const Node _) const { return x*_.y-y*_.x; }
	db operator [] (const db k){ return k*x+y; }
	Node operator * (const Node _) {
		return Node(x*_.x,_.x*y+_.y);
	}
} A[N],S[N],Pow[35];
db Cross(Node a,Node b){ return (b.y-a.y)/(a.x-b.x); }
int T;

int main(){
	n=rd(),k=rd<ll>();
	rep(i,1,n) {
		db a=rd(),b=rd(),p;scanf("%lf",&p);
		cmax(m,p*b),A[i]=Node(1-p,a*p);
	}
	rep(i,1,n) A[i].y=m-A[i].y;
	sort(A+1,A+n+1);
	rep(i,1,n) {
		while(T>1 && ((A[i]-S[T])^(S[T-1]-S[T]))<eps) T--;
		S[++T]=A[i];
	}
	db g=0,s=k*m;
	S[0].y=1e40;
	while(k) {
		while(T>1 && S[T-1][g]<=S[T][g]+eps) T--;
		Pow[0]=S[T];
		for(int i=1;(1ll<<i)<=k;++i) Pow[i]=Pow[i-1]*Pow[i-1];
		drep(i,34,0) if((1ll<<i)<=k && S[T-1][Pow[i][g]]>=S[T][Pow[i][g]]+eps) k-=1ll<<i,g=Pow[i][g];
		if(k && S[T-1][g]>=S[T][g]+eps) k--,g=Pow[0][g];
	}
	printf("%.10lf\n",s-g);
}