提高培优班Day18T2题解

常规
,
1

题意

给定 n 个价值不同的元素，维护一个初始为空的可重集合。如果集合为空，则等概率地获得一个元素。如果集合不为空，则有 p 的概率删除集合中最小的一个元素，或者 1−p 的概率获得一个随机的元素，并且该元素的价值不大于集合中的任何一个元素，即小于等于集合中最小元素。求整个集合的元素价值之和大于 t 的期望步数。

Solution

发现对于某一种状态，去掉一个元素后的状态是唯一的，而添加一个元素后则可能有多种后继状态，类似树的结构，故考虑对于状态建树。对于每个节点 i ，定义其前驱节点为 pre_i ，其后继节点为 suc_i 。令 dp_{\mathtt{S}} 为当前集合为 \mathtt{S} 时的期望步数，则可以写出转移方程：

dp_{\mathtt{S}} = 1 + p \times dp_{pre_{\mathtt{S}}} + \dfrac{1-p}{ \mid suc \mid } \times \sum_{ v \in suc_{\mathtt{S}}} dp_v

且对于叶子节点，由于其没有后继节点，则有：

dp_{\mathtt{S}} = p \times dp_{pre_{\mathtt{S}}} +1

发现 dp_{\mathtt{S}} 和 dp_{pre_{\mathtt{S}}} 是线性关系，故推断所有子节点和父节点都是线性关系。设 dp_{\mathtt{S}}=k_{\mathtt{S}}\times dp_{pre_{\mathtt{S}}}+b_{\mathtt{S}} ，则代换后有

dp_{\mathtt{S}} = 1 + p \times dp_{pre_{\mathtt{S}}} + \dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} ( k_v \times dp_{\mathtt{S}} + b_v )
dp_{\mathtt{S}} = 1 + p \times dp_{pre_{\mathtt{S}}} + \dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} b_v + dp_{\mathtt{S}}\times \dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} k_v

移项：

dp_{\mathtt{S}} \times ( 1-\dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} k_v)= p \times dp_{pre_{\mathtt{S}}} + \dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} b_v + 1

将式子化成 dp_{\mathtt{S}}=k_{\mathtt{S}}\times dp_{pre_{\mathtt{S}}}+b_{\mathtt{S}} 形式：

dp_{\mathtt{S}} = \dfrac{p}{ 1-\dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} k_v } \times dp_{pre_{\mathtt{S}}} + \dfrac{ \dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} b_v + 1 }{ 1-\dfrac{ 1 - p }{\mid suc \mid} \times \sum_{ v \in suc_{\mathtt{S}}} k_v }

一遍 DFS 即可求出所有节点的 k_{\mathtt{S}} 以及 b_{\mathtt{S}} 。答案即为 dp_{\emptyset} ，发现对于空集，其没有前驱节点，即 dp_{pre_{\emptyset}} 为 $0$，答案即为 b_{\emptyset} 。

code

#include<bits/stdc++.h>
inline int read()
{
	int res=0,flag=1;
	char ch=getchar();
	while(!isalnum(ch)) (ch=='-')?flag=-1:1,ch=getchar();
	while(isalnum(ch)) res=res*10+ch-'0',ch=getchar();
	return res*flag;
}
int n,goal;
int val[50];
double p;
std::pair<double,double> dfs(int min,int sum)
{
	if(sum>goal)
		return std::make_pair(0.0,0.0);
	double sumk=0,sumb=0,tmp=(1-p)/min;
	for(int i=1;i<=min;i++)
	{
		std::pair<double,double> ans=dfs(i,sum+val[i]);
		sumk+=ans.first;
		sumb+=ans.second;
    }
	if(sum==0)
		tmp=1.0/min;
	sumk=1-tmp*sumk;
	sumb=1.0+tmp*sumb;
	return std::make_pair(p/sumk,sumb/sumk);
}
int main(int argc,const char *argv[])
{
	while(scanf("%lf",&p)!=EOF)
	{
		goal=read(),n=read();
		for(int i=1;i<=n;i++)
			val[i]=read();
		std::sort(val+1,val+n+1);
		printf("%.3f\n",dfs(n,0).second);
	}
	return 0;
}
2 个赞