题解 P7144

dead_X · 2023-02-28 16:21:13 · 题解

前言

THUPC 将近，写写大模拟。

题解

假设现在是 A 的回合，考虑有用的状态只有这些：

A 有 n 点血，B 有 m 点血。
A 有 n 张手牌，B 有 m 张手牌。
A 有 t_1 张没攻击过的，有 1 点血的桌面牌。
A 有 n_1 张攻击过的，有 1 点血的桌面牌。
A 有 t_2 张没攻击过的，有 2 点血的桌面牌。
A 有 n_2 张攻击过的，有 2 点血的桌面牌。
B 有 m_1 张有 1 点血的桌面牌。
B 有 m_2 张有 2 点血的桌面牌。
A 还能进行抽牌和打牌共 o 次。
A 本回合是否已经进行过至少一次操作。

考虑状态数总和只有 20^4\times 15^3\times 5\times 6\times 2，可以接受，于是直接进行记忆化搜索，结果 TLE 了（悲）

事实上在进行出牌操作时，我们需要枚举三步随机攻击的情况，将最后一步（如果你的实现足够精细，可以是最后两步）的结果也加入记忆化，时间常数显著降低，可以通过。

代码

变量名和上面是一样的，我觉得比另一篇可读。

// Problem: P7144 [THUPC2021 初赛] 狗蛋和二五仔
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P7144
// Memory Limit: 1 MB
// Time Limit: 20000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//不回家了，我们去鸟巢！
#include<bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int T=read(),o=read();
#define double float
double ans[20][20][4][4][15][15][15][6][2];
double tmp[20][20][4][4][15][15][15][6][1];
bool vis[20][20][4][4][15][15][15][6][2];
bool v1[20][20][4][4][15][15][15][6][1];
#define F(x,y) ((x*(11-x))>>1)+y
double dfs(int n,int m,int x,int y,int t1,int n1,
int t2,int n2,int m1,int m2,int d,int flg);
double att(int n,int m,int x,int y,int t1,int n1,
int t2,int n2,int m1,int m2,int d,int tm)
{
    if(n<=0) return 0;
    if(m<=0) return 1;
    if(tm==0) return dfs(n,m,x-1,y,t1,n1,t2,n2+1,m1,m2,d,1);
    if(tm==1&&v1[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][tm-1])
    return tmp[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][tm-1];
    int tot=2+t1+n1+t2+n2+m1+m2;
    double res=0;
    res+=att(n-1,m,x,y,t1,n1,t2,n2,m1,m2,d,tm-1);
    res+=att(n,m-1,x,y,t1,n1,t2,n2,m1,m2,d,tm-1);
    if(t1) res+=t1*att(n,m,x,y,t1-1,n1,t2,n2,m1,m2,d,tm-1);
    if(n1) res+=n1*att(n,m,x,y,t1,n1-1,t2,n2,m1,m2,d,tm-1);
    if(t2) res+=t2*att(n,m,x,y,t1+1,n1,t2-1,n2,m1,m2,d,tm-1);
    if(n2) res+=n2*att(n,m,x,y,t1,n1+1,t2,n2-1,m1,m2,d,tm-1);
    if(m1) res+=m1*att(n,m,x,y,t1,n1,t2,n2,m1-1,m2,d,tm-1);
    if(m2) res+=m2*att(n,m,x,y,t1,n1,t2,n2,m1+1,m2-1,d,tm-1);
    if(tm>=2) return res/tot;
    v1[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][tm-1]=1;
    return tmp[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][tm-1]=res/tot;
}
double dfs(int n,int m,int x,int y,int t1,int n1,
int t2,int n2,int m1,int m2,int d,int flg=0)
{
    if(n<=0) return 0;
    if(m<=0) return 1;
    if(vis[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][flg])
        return ans[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][flg];
    double &res=ans[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][flg];
    if(n>2&&x<3&&d)
        res=max(res,dfs(n-2,m,x+1,y,t1,n1,t2,n2,m1,m2,d-1,1));
    if(t1&&m1)
        res=max(res,dfs(n,m,x,y,t1-1,n1,t2,n2,m1-1,m2,d,1));
    if(t1&&m2)
        res=max(res,dfs(n,m,x,y,t1-1,n1,t2,n2,m1,m2-1,d,1));
    if(t1)
        res=max(res,dfs(n,m-3,x,y,t1-1,n1+1,t2,n2,m1,m2,d,1));
    if(t2&&m1)
        res=max(res,dfs(n,m,x,y,t1,n1,t2-1,n2,m1-1,m2,d,1));
    if(t2&&m2)
        res=max(res,dfs(n,m,x,y,t1,n1,t2-1,n2,m1,m2-1,d,1));
    if(t2)
        res=max(res,dfs(n,m-3,x,y,t1,n1,t2-1,n2+1,m1,m2,d,1));
    if(x&&t1+n1+t2+n2<4&&d)
        res=max(res,att(n,m,x,y,t1,n1,t2,n2,m1,m2,d-1,3));
    if(flg)
        res=max(res,1-dfs(m,n,min(y+1,3),x,m1,0,m2,0,t1+n1,t2+n2,o));
    vis[n-1][m-1][x][y][F(t1,n1)][F(t2,n2)][F(m1,m2)][d][flg]=1;
    return res;
}
signed main()
{
    while(T--)
    {
        int n=read(),m=read();
        int a[2]={0,0},b[2]={0,0};
        for(int s=read(); s--; ++b[read()-1]);
        for(int s=read(); s--; ++a[read()-1]);
        int y=read(),x=read();
        printf("%.9lf\n",dfs(n,m,min(x+1,3),y,a[0],0,a[1],0,b[0],b[1],o));
    }
    return 0;
}