题目概述

本题要求计算滑铁卢野鹅队和劳里埃金鹰队之间可能发生的同城德比比赛中，两队得分总和的最大值。

---

问题分析

核心约束条件

一场比赛成为同城德比必须满足以下条件：

1. 胜负关系一致性：一场比赛有且仅有一个胜者

   • 如果野鹅队获胜（$S_i = \texttt{W}$），则金鹰队必须输（$T_j = \texttt{L}$）
   • 如果野鹅队输（$S_i = \texttt{L}$），则金鹰队必须赢（$T_j = \texttt{W}$）

2. 得分关系一致性：

   • 如果野鹅队赢，则必须有 $A_i > B_j$
   • 如果野鹅队输，则必须有 $A_i < B_j$

问题转化

我们需要从两个序列中选取若干对比赛 $(i, j)$，使得：

1. 每场比赛最多被选择一次
2. 所有选出的比赛对都满足上述约束条件
3. 最大化所有比赛对得分总和 $\sum (A_i + B_j)$

这本质上是带权匹配问题，但由于序列有序性限制，可以转化为二维动态规划。

---

算法思路

动态规划状态设计

设 $dp[i][j]$ 表示考虑野鹅队前 $i$ 场比赛和金鹰队前 $j$ 场比赛时，能获得的最大得分总和。

状态转移方程

对于每一对 $(i, j)$，有三种情况：

1. 不匹配野鹅队的第 $i$ 场比赛：

   $$dp[i][j] = \max(dp[i][j], dp[i-1][j])$$

2. 不匹配金鹰队的第 $j$ 场比赛：

   $$dp[i][j] = \max(dp[i][j], dp[i][j-1])$$

3. 匹配野鹅队第 $i$ 场和金鹰队第 $j$ 场（需满足匹配条件）：

   $$\text{if } \text{match}(i, j) \text{ then } dp[i][j] = \max(dp[i][j], dp[i-1][j-1] + A_i + B_j) $$

其中匹配条件 $\text{match}(i, j)$ 定义为：

$$\text{match}(i, j) = \begin{cases} \text{true} & \text{if } (S_i = \texttt{W} \land T_j = \texttt{L} \land A_i > B_j) \\ \text{true} & \text{if } (S_i = \texttt{L} \land T_j = \texttt{W} \land A_i < B_j) \\ \text{false} & \text{otherwise} \end{cases} $$

边界条件

• $dp[0][j] = 0$（没有野鹅队的比赛）
• $dp[i][0] = 0$（没有金鹰队的比赛）

---

算法实现细节

复杂度分析

• 时间复杂度：$O(N^2)$，需要填充 $N \times N$ 的 DP 表
• 空间复杂度：$O(N^2)$，可以使用滚动数组优化到 $O(N)$

关键优化

由于 $N \leq 1000$，$O(N^2)$ 的算法完全可行（约 $10^6$ 次操作）。

---

样例解析

样例 1

输入：
1
W
2
W
3

输出：0

分析：两队都赢了比赛，无法匹配（同城德比必须一胜一负），因此最大得分和为 0。

样例 2

输入：
4
WLLW
1 2 3 4
LWWL
6 5 3 2

输出：14

匹配方案：

1. 野鹅队第 3 场（输，得 3 分）匹配金鹰队第 2 场（赢，得 5 分）
2. 野鹅队第 4 场（赢，得 4 分）匹配金鹰队第 4 场（输，得 2 分）

得分总和：$3 + 5 + 4 + 2 = 14$

---

算法正确性证明

1. 无后效性保证

动态规划的状态只依赖于之前的状态 $(i-1, j)$、$(i, j-1)$ 和 $(i-1, j-1)$，满足无后效性。

2. 最优子结构

如果 $dp[i][j]$ 是最优解，那么其子问题 $dp[i-1][j]$、$dp[i][j-1]$ 或 $dp[i-1][j-1]$ 也必然是最优解。

3. 匹配条件完备性

匹配条件 $\text{match}(i, j)$ 严格对应了题目中同城德比的定义，确保只有合法的比赛对才会被匹配。

---

扩展思考

1. 如果允许平局？

题目明确说明不会有平局，因此算法中无需考虑平局情况。

2. 更大数据范围

如果 $N$ 增大到 $10^5$，$O(N^2)$ 算法将不可行。此时可以考虑更高效的算法，如基于贪心或网络流的方法。

---

总结

本题通过二维动态规划优雅地解决了比赛匹配问题，核心在于：

1. 将问题转化为序列匹配问题
2. 设计满足题目约束的匹配条件
3. 利用动态规划高效求解最大得分和

算法简洁高效，充分体现了动态规划在解决有序序列匹配问题中的强大能力。

---

算法标签：动态规划、递推、序列匹配