又来水一篇题解,思路在注释里

#include<bits/stdc++.h>
using namespace std;
double a[130][130],f[8][130];
int n,m;
int main()
{
	while(scanf("%d",&n)!=EOF&&n!=-1)
	{
		int m=1<<n;//几支队伍 
		for(int i=0;i<m;i++)for(int j=0;j<m;j++)scanf("%lf",&a[i][j]);
		memset(f,0,sizeof(f));
		for(int i=0;i<m;i++)f[0][i]=1;//第0轮一定胜出(一开始都在)
		for(int i=1;i<=n;i++)for(int j=0;j<m;j++)
		{
			for(int k=0;k<m;k++)
			{
				if(((j>>(i-1))^1)==(k>>(i-1)))
					//判断j和k可不可以在第i轮相遇(别问我是怎么得到这个公式的) 
					f[i][j]+=f[i-1][j]*f[i-1][k]*a[j][k];//上一轮两只队伍都得胜出 
			}
		}
		int id=0;
		for(int i=1;i<m;i++)if(f[n][id]<f[n][i])id=i;//找答案 
		printf("%d\n",id+1);//加1是因为题目中要求1~m,代码中是0~m-1 
	}
	return 0;
}

E39 概率DP 求概率

#include<bits/stdc++.h>
using namespace std;

double p[130][130],f[8][130];
int main()
{
	int n,m;
	while(scanf("%d",&n)!=EOF && n!=-1)
	{
		int m=1<<n;
		for(int i=0;i<m;i++) for(int j=0;j<m;j++) scanf("%lf",&p[i][j]);
		for(int i=0;i<m;i++) f[0][i]=1;
		
		for(int i=1;i<=n;i++)
			for(int j=0;j<m;j++)
			{
				f[i][j]=0;
				for(int k=0;k<m;k++)
				if( ((j>>(i-1))^1) == (k>>(i-1))   ) //秒：j和k能在第i轮相遇的条件
				{
					f[i][j]+=f[i-1][j]*p[j][k]*f[i-1][k];
				}
			}
		int x=0;for(int i=1;i<m;i++) if( f[n][x]<f[n][i]) x=i;
		printf("%d\n",x+1);
	}
	
	return 0;
}

E39 概率DP 求概率

#include<bits/stdc++.h>
using namespace std;

double p[130][130],f[8][130];
int main()
{
	int n,m;
	while(scanf("%d",&n)!=EOF && n!=-1)
	{
		int m=1<<n;
		for(int i=0;i<m;i++) for(int j=0;j<m;j++) scanf("%lf",&p[i][j]);
		for(int i=0;i<m;i++) f[0][i]=1;
		
		for(int i=1;i<=n;i++)
			for(int j=0;j<m;j++)
			{
				f[i][j]=0;
				for(int k=0;k<m;k++)
				if( ((j>>(i-1))^1) == (k>>(i-1))   ) //秒：j和k能在第i轮相遇的条件
				{
					f[i][j]+=f[i-1][j]*p[j][k]*f[i-1][k];
				}
			}
		int x=0;for(int i=1;i<m;i++) if( f[n][x]<f[n][i]) x=i;
		printf("%d\n",x+1);
	}
	
	return 0;
}