您现在的位置是:首页 > 正文

概率/期望dp

2024-04-01 05:01:28阅读 2

 思维方式

概率/期望dp都是分析从当前状态能否去到其他情况,然后进行期望/概率公式的运算,最后消元推导出一般式。

​​​​​​Problem - 4089 (hdu.edu.cn)

思路:概率dp,正推

  1. 分类讨论,设dp[i][j]表示i人的队伍在第j个位置时事件发生的期望
    1. 首先,我们清楚,如果在dp[i][j]发生事件1,到达的状态还是dp[i][j],情况不变,所以可以把该情况移到左式再等式同除1-p1
    2. j=1,有dp[i][1]=\frac{p2*dp[i][i]+p4}{1-p1},我们如果发生事件2,你们就会到达i人队伍并排在最后的情况的期望,如果事件4,因为在k内,直接计入贡献
    3. 1<j<=k,有dp[i][j]=\frac{p2*dp[i][j-1]+p3*dp[i-1][j-1]+p4}{1-p1},发生事件2,我们到达i人队伍前进一维的状态,事件3队伍-1人,我们也是进一位,事件4在k内直接计入贡献
    4. j>k,有dp[i][j]=\frac{p2*dp[i][j-1]+p3*dp[i-1][j-1]}{1-p1},就是少了个事件4的贡献而已。
  2. 我们现在只有推导时求dp[i][1]时,dp[i][i]未知,这个是好解决的。dp[i][1]到dp[i][i]一共有i条式子,i个变量,我们可以全部联立即可消元得到dp[i][i],对于dp[i][j],我们可以看成是dp[i][j]=p*dp[i][j-1]+tmp,最后消元得到dp[i][i]就是dp[i][i]=p^{i}*dp[i][i]+tmp'观察到p就是p2/(1-p1)
  3. 我们注意到有除法1-p1与1-p1-p2,显然,不能除0,所以特判他们为0直接结束。
#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
const int N = 2e3 + 10;
double dp[N][N];
void mysolve()
{
	int n,m,k;
	double p1,p2,p3,p4;
	while(cin>>n>>m>>k>>p1>>p2>>p3>>p4)
		{
			if(1-fabs(p1+p2)<1e-6)//特判
				{
					cout<<"0.00000"<<endl;
					continue;
				}
			dp[1][1]=p4/(1-p1-p2);
			double p21=p2/(1-p1),p31=p3/(1-p1),p41=p4/(1-p1);//简化公式
			for(int i=2; i<=n; ++i)
				{
					double p=p21,tmp=p41;
					for(int j=2; j<=i; ++j)
						{
							p*=p21,tmp=tmp*p21+p31*dp[i-1][j-1];
							if(j<=k)tmp+=p41;//累加获得p'与tmp'
						}
					dp[i][i]=tmp/(1-p);//得到p[i][i]
					dp[i][1]=p21*dp[i][i]+p41;//获得p[i][1]
					for(int j=2; j<i; ++j)//可以正推了
						{
							dp[i][j]=p21*dp[i][j-1]+p31*dp[i-1][j-1];
							if(j<=k)dp[i][j]+=p41;
						}
				}
			printf("%.5lf\n",dp[n][m]);
		}
}

int32_t main()
{
	mysolve();
	return 0;
}

Problem - 4035 (hdu.edu.cn)

思路:树上期望

  1. ,分类讨论节点可能进入的状态,设p1为被杀概率,p2为逃生概率,cnt为该节点连接的其它点的数量。
    1. 有(1-p1-p2)的概率去往其他节点,去每个点的概率都是1/cnt
    2. 有p2概率逃生,得到期望p2*0=0。
    3. 有p1的概率被杀,回到点1,得到期望p1*dp[1]。  
  2. 显然,最后dp公式可以写成dp[i]=xdp[1]+ydp[父]+k(k为常数)。看似有2个未知量,但是每次ydp[父]转移到父代后就成为常数,而最终的dp[1]=x'dp[1]+0+k(没有父亲),所以dp[1]=k/(1-x')
#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
const int N = 1e4 + 10;
double f1[N],f2[N],f3[N];
vector<int>edge[N];
double p1[N],p2[N];

void dfs(int u,int f)
{
	double cnt=0.0,son=0.0;//都设置为浮点数,cnt为整形会wa
	if(u!=1)cnt++;//加一个父节点
	for(auto v:edge[u])if(v!=f)
			{
				dfs(v,u);
				f1[u]+=f1[v],son+=f2[v],f3[u]+=f3[v];//继承子代们的各项系数
				cnt++;
			}
	double y=1-p1[u]-p2[u],p=1.0;
	if(cnt>0.0)p=1-y*son/cnt;
	f1[u]=(y*f1[u]/cnt+p1[u])/p;
	if(cnt>0.0)f2[u]=y/cnt/p;
	f3[u]=y*(f3[u]/cnt+1)/p;
}
int tt=0;
void mysolve()
{
	int n,x,y;
	cin>>n;
	for(int i=1; i<=n; ++i)edge[i].clear(),f1[i]=f2[i]=f3[i]=0.0;//期望涉及前后关系,每次都要记得初始化
	for(int i=1; i<n; ++i)scanf("%d %d",&x,&y),edge[x].push_back(y),edge[y].push_back(x);
	for(int i=1; i<=n; ++i)scanf("%lf %lf",&p1[i],&p2[i]),p1[i]/=100.0,p2[i]/=100.0;
	dfs(1,0);
	cout<<"Case "<<++tt<<": ";
	if(fabs(f1[1]-1.0)<1e-9)
		{
			cout<<"impossible"<<endl;
		}
	else
		{
			double ans=f3[1]/(1-f1[1]);
			printf("%.6lf\n",ans);
		}
}

int32_t main()
{
	ll t=1;
	cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

Problem - 6656 (hdu.edu.cn)

思路:期望dp,正推

  1. 首先,显然的是,去x点之前,必须经过x-1点,所以,我们求l到r,可以等于dp[r]-dp[l](dp[i]表示从1级升到i级需要的期望)
  2. 显然,我们可以从低级推到高级,当前dp[i]已知,求dp[i+1],那么dp[i+1]=a[i]+dp[i]+(1-p)*(dp[i+1]-dp[x[i]]),即dp[i+1]=\frac{a[i]+dp[i]}{p[i]}+(1-\frac{1}{p[i]})*dp[x[i]]分析一下,我们去dp[i+1],无论成功与否,都需到达dp[i]的期望+升级一次的代价,加上还有(1-pi)的概率会去dp[xi],那么从xi到i+1,需要的期望就是dp[i+1]-dp[xi],所以有(1-pi)的概率额外增加消耗dp[x+1]-dp[xi]
#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
#define endll            endl<<endl
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
//double 型memset最大127,最小128
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 5e5 + 10;
const int mod=1e9+7;
int dp[N];
int r[N],s[N],x[N],a[N];

ll fastmi(ll base,ll power)
{
	ll ans=1;
	while(power)
		{
			if(power&1)ans=ans*base%mod;
			power>>=1,base=base*base%mod;
		}
	return ans;
}
void mysolve()
{
	int n,q;
	cin>>n>>q;
	for(int i=1; i<=n; ++i)cin>>r[i]>>s[i]>>x[i]>>a[i];
	dp[1]=0;
	for(int i=1; i<=n; ++i)
		{
			int p1=s[i]*fastmi(r[i],mod-2)%mod;//p1是1/pi
			dp[i+1]=((a[i]+dp[i])*p1%mod+(1-p1+mod)%mod*dp[x[i]]%mod)%mod;
		}
	int x,y;
	while(q--)
		{
			cin>>x>>y;
			cout<<(dp[y]-dp[x]+mod)%mod<<endl;
		}
}

int32_t main()
{
	std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

Problem - 1145 (hdu.edu.cn)

思路:期望dp,倒推

  1. 我们设dp[i]为考虑了前面n-i题的情况下的答题期望。
  2. 假设当前答对了i道题,那么他答不答i+1道,取决于答完是否期望会比答对i道的奖金高(2^i),那么他需要知道答对i+1道的期望,如果pi*dp[i+1]>=2^i,那么答题。
  3. 因此,我们每次求i,都是需要知道后面的答题期望才可确认是否答题,倒推即可。
  4. 显然,dp[n]=2^n,因为它后面没有题需要考虑,答对n道就是n道的奖金
  5. 因为给定p是答对概率在(p,1)波动,所以,如果p<pi时,我们显然不要答题,保留得到i道题的奖金(2^i),否则答题,得到pi*dp[i+1]的奖金
#include <bits/stdc++.h>
using namespace std;
#define ll               long long
#define endl             "\n"
#define int              long long
#define endll            endl<<endl
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<long long, long long> pll;
//---------------------------------------------------------------------------------------------------------------------//
//---------------------------------------------------------------------------------------------------------------------//
//double 型memset最大127,最小128
const int INF = 0x3f3f3f3f;         //int型的INF
const ll llINF = 0x3f3f3f3f3f3f3f3f;//ll型的llINF
const int N = 35;
double dp[N];
int pre[N];
void mysolve()
{
	int n;
	double p;
	pre[0]=1;
	for(int i=1; i<=30; ++i)pre[i]=2*pre[i-1];
	while(cin>>n>>p&&(n||fabs(p)>1e-9))
		{
			dp[n]=pre[n];
			for(int i=n-1; i>=0; --i)
				{
					double tmp=pre[i]/dp[i+1];//答题与否的分界线
					if(p>=tmp)//大于就答题
						{
							dp[i]=(p+1)/2*dp[i+1];//因为是p~1的平均期望,取中间值
						}
					else
						{
							dp[i]=(tmp-p)/(1-p)*pre[i]+(1-tmp)/(1-p)*(tmp+1)/2*dp[i+1];//在p<tmp的情况下不答,发生概率是(tmp-p)/(1-p),剩下就是答题
						}
				}
			printf("%.3lf\n",dp[0]);
		}
}

int32_t main()
{
	//std::ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	ll t=1;
	//cin >> t;
	while (t--)
		{
			mysolve();
		}
	system("pause");
	return 0;
}

网站文章

  • MyBatis与Spring整合

    MyBatis与Spring整合

    MyBatis与Spring整合相关文档配置文件Mybatis全局配置文件映射文件SpringMVCweb.xmlSpring配置Spring MVC 配置spring-servlet.xmlcont...

    2024-04-01 05:00:48
  • hibernate查询方式

    1、OID(主键)查询 使用get方法 Customer customer=session.get(Customer.class,1l); 使用load方法 Customer customer=session.load(Customer.class,1l);2、对象导航检索: hibernate根据一个已经查到的对象,获得其关...

    2024-04-01 05:00:40
  • 【第四章】

    笔记记录

    2024-04-01 05:00:32
  • 解决git每次拉取/提交代码时都需要输入用户名和密码的方法

    解决git每次拉取/提交代码时都需要输入用户名和密码的方法

    2024-04-01 05:00:22
  • 如何在移动端测试Vue项目?

    如何在移动端测试Vue项目?

    第一步,打开cmd,输入ipconfig 我们获取到方框内的端口号,比如 xx.xx.x.xxx 我们打开项目中的config/index.js ,将这个替换其中的host 比如我们之前需要的是localhost:8888/news.html 那么我们将服务运行起来之后,就变成了 xx.xx.x.xxx:8888/news.html 如果你觉得在手机浏览器上手动输入很麻烦,那么...

    2024-04-01 04:59:42
  • APP为什么用JSON协议与服务端交互:序列化相关知识

    APP为什么用JSON协议与服务端交互:序列化相关知识

    Avro支持的数据类型非常丰富,包括C++语言里面的union类型。SOAP具有安全、可扩展、跨语言、跨平台、支持多种传输协议,有广泛的群众基础,基于HTTP的传输协议使得SOAP在穿越防火墙时具有良...

    2024-04-01 04:59:34
  • 练习7-1 编写一个程序 实现大写字母转换成小写字母,小写字母转换成大写字母 热门推荐

    #include&lt;stdlib.h&gt; #include&lt;ctype.h&gt; #include&lt;stdio.h&gt; char to_lower(char c); int main() { int c; while((c = getchar()) != EOF) putchar(to_lower(c)); return 0; } ...

    2024-04-01 04:59:26
  • 设置PPT版式

    设置PPT版式

    1.点击视图,幻灯片母版2.选中某个PPT母版,可进行编辑转载于:https://www.cnblogs.com/RogerLu/p/11495353.html

    2024-04-01 04:58:49
  • mac笔记本修改 mysql 的密码

    第一种mysql版本:5.7.171.首先我们要关闭mysql服务sudo /usr/local/mysql/support-files/mysql.server stop2.我们要用安全模式启动mysqlsudo /usr/local/mysql/bin/mysqld_safe --skip-grant-tables3.使用root账号登录mysql服务/usr/local/mys...

    2024-04-01 04:58:42
  • Synergy两台电脑使用同一个鼠标和键盘 热门推荐

    Synergy两台电脑使用同一个鼠标和键盘 热门推荐

    分享一款共享鼠标和键盘的软件,即两台电脑使用同一个鼠标和键盘!Synergy是一款跨平台的键盘鼠标共享软件,日前我们提供了Synergy 和Synergy 64位的Win版本、Synergy Mac版...

    2024-04-01 04:58:35