当前位置: 首页 > 工具软件 > Fish Sync > 使用案例 >

洛谷-Fish-(概率+状压dp)

晋承嗣
2023-12-01

CF16E

题意:
就是给你n<=18条鱼,彼此相遇的概率是一样的,如果鱼i和鱼j相遇,那么i吃j概率va[i][j],j吃i概率为dp[j][i],直到只剩一条鱼。现在问你每条鱼存活到最后的概率。

思考:

  1. 刚看到这题的时候,范围很小,可以218的去枚举,但是还是无从下手。看了题解才知道是状压,确实只要是可以2的多少次方枚举的,这就是状压dp的提示
  2. 那么定义dp[i]为,到i这种状态的概率。那么最刚开始所有鱼都存活就是(1ll<<n)-1的概率为1,注意这里是倒退dp,确实所谓的倒退dp就是,要从已知的状态去推未知的状态。只要我们每次从已知往未知推就可以了。那么枚举状态i,再枚举j和k代表,j吃了k,那么d[i]可以由dp[i|(1ll<<k)]来转移,由于这个状态已经知道,所以只要✖j和k相遇的概率和j吃掉k的概率就可以了。

代码:

#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define db double
#define int long long
#define PII pair<int,int >
#define mem(a,b) memset(a,b,sizeof(a))
#define IOS std::ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);

using namespace std;
const int mod = 1e9+7,inf = 1e18;
const int N = 1e6+10,M = 110;

int T,n,m,k;
db va[M][M];
db dp[N];

signed main()
{
	IOS;
	cin>>n;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		cin>>va[i][j];
	}
	dp[(1ll<<n)-1] = 1; //最开始的状态
	for(int i=(1ll<<n)-1;i>=1;i--)
	{
		db res = 0;
		for(int j=0;j<n;j++) if(i>>j&1) res++; //一共有多少鱼
		for(int j=0;j<n;j++) //我让j吃了k
		{
			if(!(i>>j&1)) continue; //如果这个状态j没有了不行
			for(int k=0;k<n;k++)
			{
				if((i>>k&1)) continue; //如果k还活着不行
				dp[i] += dp[i|(1ll<<k)]*va[j+1][k+1]*2/res/(res+1);
			} //i|(1ll<<k)可以到状态i,概率就是j吃k,并且j和k要相遇1/C(res+1,2)
		}
	}
	for(int i=0;i<n;i++) printf("%.6lf ",dp[(1ll<<i)]);
	return 0;
}

总结:
一定要对小范围的数据有敏感,特别是2的多少次方,一定要想想这些对应的算法。

 类似资料: