[ Codeforces Round #518 ] [ CF 1067D ] Computer Game

题目大意:有\(n\)个副本,副本可以升级,每个副本有三个值\( a_i , b_i , p_i \),其中\(a_i\)表示该副本在升级前通关的奖励,\(b_i\)表示该副本在升级后通关的奖励,\(p_i\)表示通关该副本的概率。玩家总共可以挑战\(t\)次副本,当玩家挑战某一副本成功后,它可以选择任意一个副本升级(当次不享受升级优惠),求能获得奖励的最大期望。数据范围:\( 1 \leq  n \leq 10^5 , 1 \leq t \leq 10^10 , 1 \leq a_i < b_i \leq 10^8 , 0 < p_i < 1\)

notice:这篇题解是错的,待修改

题解:如果某一次挑战副本成功了,接下来一定是选择\(b_i \cdot p_i\)最大的那个升级,并一直挑战那个副本。而在此之前,我们肯定只会选择一个最佳的副本一直挑战。如果升级前挑战的副本为i,升级后挑战的副本为j,那么有\[ ans = \sum_{k=1}^{t}{(1-p_i)^{k-1} ( a_i + (n-k)p_j \cdot b_j )} \]

设\( p = p_i , q = 1 – p , a = a_i ,  c = p_j \cdot b_j \),那么化简后有\[ ans = a \cdot ( 1 – q^t ) + (t – \frac{ 1 – q^t } { p_i }) c \]

我们发现这是一个形如\( y = kx + b\)的形式,其中\(k,b\)只与第i个副本有关且k是大于等于0的(\( k = t – \frac{ 1- q^t } { p_i }\),\( p = 1 – q \),将右式展开等于\( 1 + q + q^2 + \cdots + q^{t-1} \leq t \)) ,\(x\)只与第j个副本有关,所以\(x\)一定是取最大的那个\(b_i \cdot p_i\),接下来找出最合适的那个升级前打的副本。

一个特殊情况是\(t=1\)的时候,也是唯一的\(k=0\)的时候,接下来就算升级了最大的那个x的副本也是没有用的,这时选择\( a_i \cdot p_i \)最大的那个。这种情况发生在挑战副本失败\(t-1\)次,只剩下最后一次的时候。记\( y = \max{a_i \cdot p_i}\),那么有修正后\[ans = a \cdot ( 1 – q^{t-1} ) + q^{t-1} \cdot y + (t – \frac{ 1 – q^t } { p_i }) c \]


page views : 28 views

发表评论

电子邮件地址不会被公开。 必填项已用*标注