P3239 [HNOI2015]亚瑟王期望 dp

LINK：亚瑟王

Saber！Excalibur！

比较难的期望dp.

可以发现如果暴力枚举所有的局面复杂度很高。

转换的思路则是期望的线性性。

求出每张牌的期望累加即可。

考虑每张牌的期望=这张牌使用的概率*这张牌造成的伤害。

容易得到第一张牌使用的概率=\(p_1+(1-p_1)p_1+(1-p_1)^2p_1+...\) 等比数列求和后容易得到 \(1-(1-p_1)^r\)

同样我们使用容斥也可以得到上述结果。

接下来需要求出其他牌的概率。由于题目中的条件使用了一张牌后就结束本局所以按照局数来进行dp会非常的繁杂且还需要记录到底哪张牌用过与否。

容易发现对于第i张牌有影响的是前i-1张牌。

考虑状态 f[i][j]表示在所有局数中前i张牌有j张使用的概率有了这个就可以求出某张牌的pi了。

\(w_i=1-\sum_{k=0}^{i-1}f[i-1][k]\cdot (1-p_i)^{r-k}\)

\(f[i][j]=f[i-1][j]\cdot (1-p_i)^{r-k}+f[i-1][j-1]\cdot (1-(1-p_i)^{r-k+1})\)

这样问题就得到了很好的解决需要预处理概率的幂次时间复杂度 Ntr /cy.

const int MAXN=250;

int n,T,r;

db w[MAXN][MAXN],f[MAXN][MAXN],d[MAXN],s[MAXN],ans;

inline db ksm(db b,ll p)

{

	db cnt=1;

	while(p)

	{

		if(p&1)cnt=cnt*b;

		b=b*b;p=p>>1;

	}

	return cnt;

}

int main()

{

	freopen("1.in","r",stdin);

	gt(T);

	while(T--)

	{

		gt(n);gt(r);

		rep(1,n,i)gi(s[i]),gi(d[i]);

		rep(1,n,i){w[i][0]=1;rep(1,r,j)w[i][j]=w[i][j-1]*(1-s[i]);}

		f[0][0]=1;

		rep(1,n,i)

		{

			rep(0,min(r,i),j)

			{

				f[i][j]=0;

				f[i][j]+=f[i-1][j]*w[i][r-j];

				f[i][j]+=f[i-1][j-1]*(1-w[i][r-j+1]);

			}

		}

		ans=0;

		rep(1,n,i)

		{

			db ww=1;

			rep(0,min(i-1,r),k)ww-=f[i-1][k]*w[i][r-k];

			ans=ans+ww*d[i];

		}

		printf("%.10lf\n",ans);

	}

	return 0;

}

巴特西

P3239 [HNOI2015]亚瑟王期望 dp

最新文章

热门文章

巴特西

P3239 [HNOI2015]亚瑟王 期望 dp

最新文章

热门文章

P3239 [HNOI2015]亚瑟王期望 dp