提高组T2

很多人反映这个题目看不懂啊，然后我就看了一下结果发现是我那个网球规则写得不太清楚的问题？ （还是说因为深司发球对龙马的影响如下这段话的缺少导致你们看不懂这个：

1. 如果龙马选择 策略 A（强攻）：由于手臂麻痹，精准度大幅下降，胜率 $p_1$ 变为原来的 $80\%$（即 $p_1 \times 0.8$），但耗时 $t_1$ 不变。

2. 如果龙马选择 策略 B（拉锯）：深司会故意拖慢节奏，导致每一球的耗时增加 5 秒（即 $t_2 + 5$），但胜率 $p_2$ 不受影响（因为龙马靠毅力死守）。

？）

先给你们回顾一下题目

如果没看懂的话可以回去再看看，我已经把具体规则补充上去了，接下来是此题的题解

满分做法，看不懂的可以先看下面的暴力做法

这道题是 概率 DP 结合 记忆化搜索 的典型应用。

Trick 1: 状态映射与变量修改

首先，it's very obvious that 网球的比分（"0", "15", "30", "40", "Adv"）我们可以将其映射为整数 $0 \sim 4$。 得分就是：赢一球即状态 $+1$。

对于题目中 $Who$（发球方）带来的影响，在 DP 内部反复判断显而易见是非常clever but wrong 的做法。我们直接进行预处理： 如果 $Who = 1$（深司发球），直接修改全局变量：

$$p_1 \leftarrow p_1 \times 0.8$$ $$t_2 \leftarrow t_2 + 5$$

这样后续的搜索逻辑就变得统一了。

Trick 2: 记忆化搜索

看似网球比赛在 Deuce（40-40）阶段可能无限进行下去，形成状态环。但好心的我（其实是网球王子的作者）为你们加入了总时间 $T$ 这个限制。 无论选择策略 A 还是 B，时间 $t$ 都会严格减少。因此，状态图是一个有向无环图（DAG），不存在死循环，可以直接使用记忆化搜索。

设 $dp[r][s][t]$ 表示龙马当前得分为 $r$，深司得分为 $s$，剩余时间为 $t$ 时，最终获胜的最大概率。

对于每一个状态，我们有两种决策，取最大值：

1. 选择策略 A：$$P_A = p_1 \times dfs(r+1, s, t-t_1) + (1-p_1) \times dfs(r, s+1, t-t_1) $$
2. 选择策略 B：$$P_B = p_2 \times dfs(r+1, s, t-t_2) + (1-p_2) \times dfs(r, s+1, t-t_2) $$

最终状态转移方程为：

$$dp[r][s][t] = \max(P_A, P_B)$$

边界条件判定（Exit Condition）：

1. 获胜：龙马得分 $\ge 4$ 且 净胜球 $\ge 2$，返回 $1.0$。
2. 失败：深司得分 $\ge 4$ 且 净胜球 $\ge 2$，返回 $0.0$。
3. 超时：剩余时间 $t < 0$，无法完成当前球，判负，返回 $0.0$。

结合以上两个 trick，这道题就被转化为了在一个三维状态空间上寻找最优路径的概率问题。

快乐的80分做法，但是为啥没人要

这题的暴力解法是基于最朴素的 DFS 模拟。

思路分析：

我们将比赛过程看作在状态空间中的行走。每一个状态由 (龙马得分, 深司得分, 剩余时间) 三元组唯一确定。

对于每一个非终局的状态，龙马面临两个分支：

1. 策略 A：消耗 t1 时间，转移到 (赢球/输球) 的子状态，胜率加权平均。
2. 策略 B：消耗 t2 时间，转移到 (赢球/输球) 的子状态，胜率加权平均。

根据题意，龙马会做出最优决策，因此： 当前状态胜率 = max(策略A的期望胜率, 策略B的期望胜率)。

递归边界：

1. 胜利：r >= 4 且 r - s >= 2，返回 1.0。
2. 失败：s >= 4 且 s - r >= 2，返回 0.0。
3. 超时：t < 0，返回 0.0。

复杂度分析：

比赛进入拉锯战（如 40-40 反复 Deuce），或者 T 很大时，程序会重复计算同一个状态无数次。 树的深度大约为 T / min(t1, t2)，每一层分裂出多个分支，复杂度呈指数级爆炸。 但在 T 较小或 t1, t2 较大的数据点下，搜索树规模很小，可以秒出啊。 那为什么能有80分呢，反正我绝对不会承认，是我的数据太水了

#include <bits/stdc++.h>
using namespace std;
#define int long long
string sr, ss;
int T, W, t1, t2;
double p1, p2;
int get(string s) {
	if (s == "0") return 0;
	if (s == "15") return 1;
	if (s == "30") return 2;
	if (s == "40") return 3;
	if (s == "Adv") return 4;
	return 0;
}
double dfs(int r, int s, int t) {
	if (r >= 4 && r - s >= 2) return 1.0;
	if (s >= 4 && s - r >= 2) return 0.0;
	if (t < 0) return 0.0;
	if (r > 25 || s > 25) return 0.0;
	double ra = 0, rb = 0;
	if (t >= t1) ra = p1 * dfs(r + 1, s, t - t1) + (1.0 - p1) * dfs(r, s + 1, t - t1);
	if (t >= t2) rb = p2 * dfs(r + 1, s, t - t2) + (1.0 - p2) * dfs(r, s + 1, t - t2);
	return max(ra, rb);
}
signed main() {
	//freopen("spot.in", "r", stdin);
	//freopen("spot.out", "w", stdout);
	char buf1[20], buf2[20];
	scanf("%s%s", buf1, buf2);
	sr = buf1, ss = buf2;
	scanf("%lld%lld%lld%lf%lld%lf", &T, &W, &t1, &p1, &t2, &p2);
	if (W) p1 *= 0.8, t2 += 5;
	int r = get(sr), s = get(ss);
	if (sr == "Adv") r = 4;
	if (ss == "Adv") s = 4;
	printf("%.5f\n", dfs(r, s, T));
	return 0;
}

100分的正解，其实就是多了个dp

#include <bits/stdc++.h>
using namespace std;
#define int long long
double dp[55][55][605];
bool v[55][55][605];
string sr, ss;
int T, W, t1, t2;
double p1, p2;
int get(string s) {
	if (s == "0") return 0;
	if (s == "15") return 1;
	if (s == "30") return 2;
	if (s == "40") return 3;
	if (s == "Adv") return 4;
	return 0;
}
double dfs(int r, int s, int t) {
	if (r >= 4 && r - s >= 2) return 1.0;
	if (s >= 4 && s - r >= 2) return 0.0;
	if (t < 0) return 0.0;
	if (r > 50 || s > 50) return 0.0;
	if (v[r][s][t]) return dp[r][s][t];
	double ra = 0, rb = 0;
	if (t >= t1) ra = p1 * dfs(r + 1, s, t - t1) + (1.0 - p1) * dfs(r, s + 1, t - t1);
	if (t >= t2) rb = p2 * dfs(r + 1, s, t - t2) + (1.0 - p2) * dfs(r, s + 1, t - t2);
	v[r][s][t] = 1;
	return dp[r][s][t] = max(ra, rb);
}
signed main() {
	//freopen("spot.in", "r", stdin);
	//freopen("spot.out", "w", stdout);
	char buf1[20], buf2[20];
	scanf("%s%s", buf1, buf2);
	sr = buf1, ss = buf2;
	scanf("%lld%lld%lld%lf%lld%lf", &T, &W, &t1, &p1, &t2, &p2);
	if (W) p1 *= 0.8, t2 += 5;
	int r = get(sr), s = get(ss);
	if (sr == "Adv") r = 4;
	if (ss == "Adv") s = 4;
	printf("%.5f\n", dfs(r, s, T));
	return 0;
}