题解：P17212 [ICPC 2017 Nanning R] Attacker-Defender Game
lailai0916
·
·
题解
题意简述
进攻方与防守方每回合同时选择要展示的能量。较大的一方消耗所展示的能量，并让防守方生命相应减一或加一；相等时双方同时消耗能量。求双方采用最优混合策略时，进攻方的获胜概率。
解题思路
设 f(h,d,a) 表示防守方有 h 点生命和 d 点能量、进攻方有 a 点能量时，进攻方的最优获胜概率。终止状态为：
f(h,d,a)=
\begin{cases}
1 & h=0 \\
0 & a<h \\
1 & d=0\land a\ge h
\end{cases}
第二条成立，是因为进攻方每造成一次伤害至少消耗一点能量。第三条中，防守方只能展示 0，进攻方连续展示 1 即可获胜。
只考虑 h,d\ge1 且 a\ge h 的状态。进攻方选择 x\in[1,a]，防守方选择 y\in[1,d]。固定本回合的选择后，进攻方的后续收益为：
G_{x,y}=
\begin{cases}
f(h-1,d,a-x) & x>y \\
f(h+1,d-y,a) & x<y \\
f(h,d-y,a-x) & x=y
\end{cases}
无论属于哪种情况，后继状态的 a+d 都严格减小。因此，可以按照总能量 a+d 递增预处理，构造 G 时需要的状态都已经求出。
双方同时行动，不能把这一回合写成普通的先取最大再取最小。G 是一个有限零和矩阵博弈，双方都可能需要混合策略。直接对所有状态运行单纯形法仍然偏慢，所以先完整刻画答案等于 0 或 1 的状态。
令 r(h,d) 表示让 f(h,d,a)>0 所需的最小 a。边界为：
\begin{aligned}
r(0,d) & =0 \\
r(h,0) & =h
\end{aligned}
固定防守方的选择 y，只需判断收益矩阵第 y 列是否存在正元素。进攻方有三类有意义的回应：
- 取 x=y+1，立即造成一点伤害；
- 取 x=y，双方同时消耗 y；
- 当 y\ge2 时取任意 x<y，其中 x=1 已经足够。
三类回应要求的最少初始能量分别为：
\begin{aligned}
y+1+r(h-1,d) \\
y+r(h,d-y) \\
r(h+1,d-y)
\end{aligned}
若某一列全部为零，防守方固定选择该列即可让游戏值为零。若每一列都有正元素，进攻方给所有行分配正概率后，每一列的期望收益都严格为正，游戏值也严格为正。因此：
r(h,d)=\max_{1\le y\le d}
\begin{cases}
\min\bigl(y+1+r(h-1,d),y+r(h,d-y)\bigr) & y=1 \\
\min\bigl(y+1+r(h-1,d),y+r(h,d-y),r(h+1,d-y)\bigr) & y\ge2
\end{cases}
右侧只依赖更小的 d，或同一 d 下更小的 h，所以按 d、h 递增即可预处理。若 a<r(h,d)，直接返回 0。
答案等于 1 的条件更简单：
a\ge h+d
先证充分性。进攻方始终选择 x=1。若 y=1，双方能量各减一，新状态仍满足同样的不等式；若 y>1，防守方生命加一、能量减少 y，新状态仍满足该不等式。对 d 归纳即可保证获胜。
再证必要性。设 a<h+d，进攻方选择任意 x。若 x\le d，防守方取 y=x，后继仍不满足必胜不等式。若 x>d，防守方取 y=d；此时 h\ge2，攻击后也有 a-x<(h-1)+d。按 a+d 归纳，这个回应的后继不是必胜态。因此收益矩阵不存在全为 1 的行，进攻方不能保证概率为 1。
剩下的状态满足：
r(h,d)\le a<h+d
对这些状态求矩阵博弈值。由于 G_{x,y}\in[0,1]，令 B=G+1，使所有元素严格为正。考虑防守方对应的线性规划：
\begin{aligned}
\max & \sum_{y=1}^{d}z_y \\
\text{s.t.} & \sum_{y=1}^{d}B_{x,y}z_y\le1 & 1\le x\le a \\
& z_y\ge0 & 1\le y\le d
\end{aligned}
设最优目标值为 Z。把最优解除以 Z，便得到防守方的概率分布。每一行在矩阵 B 中的期望收益都不超过 1/Z。由线性规划强对偶，进攻方也能保证至少 1/Z，所以 B 的游戏值为 1/Z，原矩阵的游戏值为：
f(h,d,a)=\frac{1}{Z}-1
所有约束右端都是 1，原点与松弛变量直接构成初始可行基。代码建立包含原变量和全部松弛变量的完整单纯形表，用 Bland 规则选择入基变量，并在最小比值相等时按基变量编号破除平局，避免退化循环。
阈值预处理需要 O(AD^2)。其余状态的矩阵至多为 A\times D；单纯形法理论最坏为指数级，但本题 A,D<50，且两个精确阈值已经跳过绝大多数状态。DP 空间复杂度为 O(A^2D)，单纯形表为 O((A+D)^2)。
正确性证明
状态边界与收益矩阵准确覆盖题目规定的三种比较结果。每个后继的总能量严格减小，所以递增预处理顺序合法。
当 $a\ge h+d$ 时，固定选择 $x=1$ 的策略在防守方所有回应后都保持归纳条件，故进攻方必胜。当 $a<h+d$ 时，防守方针对任意一行都能选出一个不属于必胜态的后继，所以矩阵博弈值不可能为一。两个阈值判断均无遗漏。
中间状态的第一回合正是矩阵 $G$ 的零和博弈。给所有收益加一只会让游戏值增加一。线性规划的可行解给出防守方的上界策略，强对偶给出相同的进攻方下界，因此 `simplex` 返回的 $1/Z-1$ 正是当前状态值。
程序对三个互斥且完备的区间分别返回 $0$、矩阵博弈值和 $1$，所以所有询问的答案正确。
## 参考代码
```cpp
#include <bits/stdc++.h>
using namespace std;
using ld=long double;
const int N=55;
const int Q=1205;
const int L=110;
const ld eps=1e-15L;
ld f[N][N][N],g[N][N],p[L][L];
int need[N][N],q[Q][3],bs[L];
void pivot(int r,int s,int m,int n)
{
ld inv=1/p[r][s];
for(int i=0;i<=n;i++)p[r][i]*=inv;
for(int i=0;i<=m;i++)
{
if(i==r)continue;
ld k=p[i][s];
if(fabsl(k)<eps)
{
p[i][s]=0;
continue;
}
for(int j=0;j<=n;j++)
{
if(j!=s)p[i][j]-=k*p[r][j];
}
p[i][s]=0;
}
bs[r]=s;
}
ld simplex(int m,int n)
{
int tot=m+n;
for(int i=0;i<=m;i++)
{
for(int j=0;j<=tot;j++)p[i][j]=0;
}
for(int i=0;i<m;i++)
{
for(int j=0;j<n;j++)p[i][j]=g[i][j]+1;
p[i][n+i]=1;
p[i][tot]=1;
bs[i]=n+i;
}
for(int i=0;i<n;i++)p[m][i]=-1;
while(1)
{
int s=-1;
for(int i=0;i<tot;i++)
{
if(p[m][i]<-eps)
{
s=i;
break;
}
}
if(s==-1)return p[m][tot];
int r=-1;
for(int i=0;i<m;i++)
{
if(p[i][s]<=eps)continue;
if(r==-1)
{
r=i;
continue;
}
ld x=p[i][tot]/p[i][s],y=p[r][tot]/p[r][s];
if(x<y-eps||(fabsl(x-y)<=eps&&bs[i]<bs[r]))r=i;
}
pivot(r,s,m,tot);
}
}
ld val(int h,int d,int a)
{
if(!h)return 1;
if(a<h)return 0;
if(!d)return 1;
return f[h][d][a];
}
ld solve(int h,int d,int a)
{
if(a<need[h][d])return 0;
if(a>=h+d)return 1;
for(int i=1;i<=a;i++)
{
for(int j=1;j<=d;j++)
{
if(i>j)g[i-1][j-1]=val(h-1,d,a-i);
else if(i<j)g[i-1][j-1]=val(h+1,d-j,a);
else g[i-1][j-1]=val(h,d-j,a-i);
}
}
ld z=simplex(a,d);
return max(0.0L,min(1/z-1,1.0L));
}
void init_need(int md,int ma)
{
int inf=ma+1;
for(int i=0;i<=ma+1;i++)
{
for(int j=0;j<=md;j++)need[i][j]=inf;
}
for(int i=0;i<=md;i++)need[0][i]=0;
for(int i=1;i<=ma+1;i++)need[i][0]=min(i,inf);
for(int i=1;i<=md;i++)
{
for(int j=1;j<=ma;j++)
{
int mx=0;
for(int k=1;k<=i;k++)
{
int mn=min(k+1+need[j-1][i],k+need[j][i-k]);
if(k>=2)mn=min(mn,need[j+1][i-k]);
mx=max(mx,min(mn,inf));
}
need[j][i]=mx;
}
}
}
void init(int md,int ma)
{
init_need(md,ma);
for(int i=2;i<=ma+md;i++)
{
for(int j=1;j<=ma;j++)
{
int d=i-j;
if(d<1||d>md)continue;
for(int k=1;k<=j;k++)f[k][d][j]=solve(k,d,j);
}
}
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(nullptr);
int T;
cin>>T;
int md=0,ma=0;
for(int i=0;i<T;i++)
{
cin>>q[i][0]>>q[i][1]>>q[i][2];
md=max(md,q[i][1]);
ma=max(ma,q[i][2]);
}
init(md,ma);
cout<<fixed<<setprecision(6);
for(int i=0;i<T;i++)cout<<val(q[i][0],q[i][1],q[i][2])<<'\n';
return 0;
}
```