自动搬运

查看原文

来自洛谷，原作者为

	dead_X Still we rise

搬运于2025-08-24 22:27:01，当前版本为作者最后更新于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;
}