专栏文章

题解：CF1067D Computer Game

bbelot
CF1067D题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@miq9yxhs
此快照首次捕获于
2025/12/04 01:22
3 个月前
此快照最后确认于
2025/12/04 01:22
3 个月前
查看原文

Computer Game

可以发现赢下一局后，会选择升级后期望收益 p×bp\times b 最高的一种游戏玩到结束位置，记 (p×b)max⁡(p\times b)_{\operatorname{max}} 为 VV 。接下来考虑升级前的策略，由于不能找出直观的贪心策略，那就使用动态规划。设 ftf_t 表示游戏还剩 tt 秒且在此之前没有赢过的期望收益最大值。可以列出转移方程：
ft=max⁡i=1n{pi(ai+(t−1)V)+ft−1(1−pi)}f_t=\max_{i=1}^n\{p_i(a_i+(t-1)V)+f_{t-1}(1-p_i)\}
这样直接转移是 O(nt)O(nt) 的，因此要优化转移。
首先把常量扔外面，再按照 i,ti, t 整理式子：
ft=max⁡i=1n{pi((t−1)V−ft−1)+piai)}+ft−1f_t=\max_{i=1}^n\{p_i((t-1)V-f_{t-1})+p_ia_i)\}+f_{t-1}
由于转移的时候 t−1,ft−1t-1, f_{t-1} 是已知的，在一步转移中可以视为常量。而 VV 也是已知常量，所以 (t−1)V−ft−1(t-1)V-f_{t-1} 在一步转移中也可以视为常量。关于 ii 的变量 pi,piaip_i, p_ia_i，与转移的量相乘与相加，这种形式可以用使用斜率优化。还有不懂斜率优化的同学可以看这里。
然后显然有 ft−ft−1≤Vf_t-f_{t-1}\leq V，所以 (t−1)V−ft−1≤tV−ft(t-1)V-f_{t-1}\leq tV-f_t，即式子中的 (t−1)V−ft−1(t-1)V-f_{t-1} 是递增的，因此可以用单指针来维护最优解在凸包上的位置，即转移是 O(1)O(1) 的。
此时的复杂度就变成了 O(n+t)O(n+t)。
然后由于 (t−1)V−ft−1(t-1)V-f_{t-1} 递增，所以游戏 ii 作为最优解的时刻一定是一个区间，则对于每一段连续的区间，可以使用矩阵加速转移。即：
[ftt1]×[1−pi00piv10piai11]=[ft+1t+11]\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(\log t) 的时间内转移一段连续的区间了。总时间复杂度 O(nlog⁡t)O(n\log t)。
Code
CPP
#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
*/

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...