P4190 [CTSC2010] 三国围棋擂台赛 题解

是青白呀 · 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;
}