自动搬运

查看原文

来自洛谷，原作者为

	是青白呀 咕咕咕？咕咕咕！

搬运于2025-08-24 21:57:30，当前版本为作者最后更新于2023-08-12 10:32:17，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

分析

根据题目中的 $n\le 7$，可以想到是将不同队伍已派出的选手的状态进行压缩，然后记忆化搜索。设 $dp_{st,x,y,i}$ 表示三个队伍已派出的选手情况为 $st$，接下来将要对战的两支队伍为 $x$ 和 $y$，且上一场胜利的队伍为 $x$，留在场上的选手为第 $i$ 号时，队伍 $y$ 按最优方案选择后 $A$ 队的胜率。每一次选择时，枚举 $y$ 队伍的所有未被派出的选手。若当前选择队员的队伍是 $A$ 队，则取所有方案中胜率最大的一个，否则取所有方案中胜率最小的一个即可。当 $A$ 队全部被淘汰，则胜率返回 $0$，当 $BC$ 两队均全部被淘汰，则胜率返回 $1$。更多细节在代码里。

这里再说一下一些小的注意事项。

• 为了便于调试，减少出错，请尽量将相近的操作写在一个函数里，用少量的 if 语句判定 不同情况，而不是用 if 语句列出所有情况，然后复制粘贴。

• 这个题需要稍稍卡一卡空间。考虑到三个队伍第一个派出的都是 $n$ 号选手，可以将前两场比赛提出来单独写，这样两场比赛之后三个队伍的 $n$ 号选手一定全部被派出，状态不变，可以不记录在 $st$ 里，$st$ 中只记录三个队伍 $1$ 至 $n-1$ 号选手的派出情况。这样可以将状态减少至原来的 $\frac{1}{8}$。

代码

#include<bits/stdc++.h>
#define rep(i,j,k) for(int i=j;i<=k;i++)
#define repp(i,j,k) for(int i=j;i>=k;i--)
#define ls(x) x*2
#define rs(x) x*2+1
#define mp make_pair
#define fir first
#define sec second
#define pii pair<int,int>
#define qingbai666 qwq
using namespace std;
const int inf=1e9+7;
typedef long long ll;
void read(int &p){
	int x=0,w=1;
	char ch=0;
	while(!isdigit(ch)){
		if(ch=='-')w=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		x=(x<<1)+(x<<3)+ch-'0';
		ch=getchar();
	}
	p=x*w;
}
double p[3][3][8][8],dp[1<<18][3][3][8];//s表示“派出” 
int n;
double chose(int st,int tx,int p,int ty);
struct data{
	int a[3];
};

data check(int st){//数三个队伍已被派出的队员数
	data ret;
	ret.a[0]=ret.a[1]=ret.a[2]=0;
	rep(i,0,2){
		rep(j,1,n-1){
			int x=i*(n-1)+j-1;
			if((st>>x)&1)ret.a[i]++;
		} 
	}
	return ret;
}
//目前在场上的选手是tx队的x号和ty队的y号。
double dfs(int st,int tx,int ty,int x,int y){
    double sit1,sit2;
    int tz=3-tx-ty;
    data ck=check(st);
    if(ck.a[tz]==n-1){//z队已经失败，x队和y队继续打 
        if(tz==0)return 0;
    	sit1=chose(st,tx,x,ty);
        sit2=chose(st,ty,y,tx);
	}
    else{
    	sit1=chose(st,tx,x,tz);
        sit2=chose(st,ty,y,tz);
	}
    return sit1*p[tx][ty][x][y]+sit2*p[ty][tx][y][x];
}
//y队伍选择将要派出的
double chose(int st,int tx,int p,int ty){
	
	if(dp[st][tx][ty][p]!=-1)return dp[st][tx][ty][p];
	data ck=check(st);
	if(ck.a[ty]==n-1){//只在仅剩两队的时候会发生这种情况 
		if(ty>0)return 1;
		else return 0;
	}
	//printf("%d %d %d %d\n",st,tx,p,ty);
	double ret;
	if(ty>0)ret=inf;
	else ret=-inf;
	rep(i,1,n-1){
		int x=ty*(n-1)+i-1;
		double sit;
		if((st>>x)&1)continue;
		sit=dfs(st|(1<<x),tx,ty,p,i);
		if(ty>0)ret=min(ret,sit);
		else ret=max(ret,sit);
	}
	//printf("%d %d %d %d:%.lf\n",st,tx,p,ty,ret);
	dp[st][tx][ty][p]=ret;
	return ret;
}

void getin(){
	rep(i,1,n){
		rep(j,1,n){
			cin>>p[0][1][i][j];
			p[1][0][j][i]=1-p[0][1][i][j];
		}
	}
	rep(i,1,n){
		rep(j,1,n){
			cin>>p[0][2][i][j];
			p[2][0][j][i]=1-p[0][2][i][j];
		}
	}
	rep(i,1,n){
		rep(j,1,n){
			cin>>p[1][2][i][j];
			p[2][1][j][i]=1-p[1][2][i][j];
		}
	}
}

int main(){
	read(n);
	getin();
	rep(i,0,(1<<18)-1){
		rep(j,0,2){
			rep(k,0,2){
				rep(l,0,7){
					dp[i][j][k][l]=-1;
				}
			}
		}
	}
	double ans=0;
	rep(i,0,1){//第一轮打 
		rep(j,i+1,2){
			int k=3-i-j;
			double sit1=dfs(0,i,k,n,n);
			double sit2=dfs(0,j,k,n,n);
			ans+=(sit1*p[i][j][n][n]+sit2*p[j][i][n][n])/3;
		}
	}
	
	printf("%.6lf\n",ans);
	return 0;
}