P12960 毒药 题解

P12960 毒药 题解

\(n\) 瓶毒药、\(n\) 瓶解药排成一排，初始血量 \(0\)。喝 A 血量 \(+1\)；喝 P 时若血量 \(=0\) 则死，否则 \(-1\)。可任选多少瓶任意交换次序，问有多少选法能活下来（对 \(10^9+7\) 取模）。
观察性子

打暴力可以发现：对固定的被选下标集合 \(S\)，最有利的排列是：把 \(S\) 中的解药放在被选位置的最前面，把 \(S\) 中的毒药放在被选位置的最后面。如许每个前缀的解药数都尽可能多；如果这种排列都致死，那 \(S\) 无论如何都不可能活。
因此只需按这种"最优排列"统计。其结构是：前面一段被选位置全是解药，后面一段被选位置全是毒药，第一个被选的毒药就是分界点，且对每个 \(S\) 唯一。
记长度 \(m=2n\)，令 \(a_i=1\)（位置 \(i\) 为 A）或 \(-1\)（位置 \(i\) 为 P）。
2. 前缀 DP \(f\)

定义 \(f_{i,j}\)：考虑前 \(i\) 个位置，把其中选中的位置都当作解药（+1），不选中的位置保持原值（\(a_i\)），要求过程中血量（前缀和）始终非负，且处理完前 \(i\) 个位置后血量为 \(j\) 的方案数。
第 \(i\) 个位置转移：

• 不选它：血量变化为实际值 \(a_i\)，由 \(f_{i-1,\,j-a_i}\) 转移（需 \(j\ge a_i\)）；
  
• 选它：当作解药，血量 \(+1\)，由 \(f_{i-1,\,j-1}\) 转移（需 \(j\ge 1\)）。
  

即

\[f_{i,j}=[j\ge a_i]\,f_{i-1,\,j-a_i}+[j\ge 1]\,f_{i-1,\,j-1}\]
越界或不满足非负的状态视为 \(0\)。初值 \(f_{0,0}=1\)。
3. 后缀 DP \(g\)

定义 \(g_{i,j}\)：考虑后缀 \([i,m]\)，把其中选中的位置都当作毒药（−1），不选中的位置保持原值，要求这个后缀的每个非空后缀中"毒药数 − 解药数"\(\ge 0\)，且整个后缀的该差值为 \(j\) 的方案数。从右往左转移：

• 不选它：由 \(g_{i+1,\,j+a_i}\) 转移（需 \(j + a_i\ge 0\)）；
  
• 选它：当作毒药，由 \(g_{i+1,\,j-1}\) 转移（需 \(j\ge 1\)）。
  

即

\[g_{i,j}=[j + a_i\ge 0]\,g_{i+1,\,j+a_i}+[j\ge 1]\,g_{i+1,\,j-1}\]
同样只保留 \(j\ge 0\) 的状态。初值 \(g_{m+1,0}=1\)。
4. 归并答案

按"最优排列里有没有出现被选的毒药"分类：

• 没有被选的毒药（所有选中位置都当解药）：方案由 \(f_{m,0}\) 统计；
  
• 有被选的毒药：设第一个被选的毒药在位置 \(i+1\)（\(0\le i\le m-1\)）。位置 \(1..i\) 选中位置全当解药，由 \(f_{i,j}\) 统计，且必须 \(j\ge 1\)（紧接要喝一瓶毒药，喝前血量至少 \(1\) 才能降到 \(\ge 0\)）；位置 \(i+1\) 是那瓶毒药，血量由 \(j\) 变 \(j-1\)；位置 \(i+2..m\) 选中位置全当毒药，由 \(g_{i+2,\,j-1}\) 统计。
  

分界点 \(i+1\) 对每种方案唯一，故直接相乘求和：

\[\mathrm{ans}=f_{m,0}+\sum_{i=0}^{m-1}\sum_{j=1}^{m}f_{i,j}\cdot g_{i+2,\,j-1}\pmod{10^9+7}\]

唯一性：若前缀里夹了被选的毒药（不是真正的"第一个"），按解药处理会虚增前缀血量，导致进入后缀时的 \(j-1\) 与实际不符，\(g\) 侧不会把它计为合法，因此不重复统计。

5. 复杂度

两个 DP 与归并均为 \(O(m^2)=O(n^2)\) 时间；
状态 \(O(m^2)\) 空间（约 \(6000^2\) 个 int，内存足够）。
6. AC code

[code]#include using namespace std;using ll = long long;const int N = 6e3 + 5;const ll MOD = 1e9 + 7;ll n; ll a[N];string s;int f[N][N], g[N][N];int main () {    freopen("poison.in", "r", stdin);    freopen("poison.out", "w", stdout);    ios::sync_with_stdio(false);    cin.tie(0);    cin >> n;    cin >> s;    s = '#' + s;    for (int i = 1; i