一个一个填过去，显然对之后有影响的是当前的后缀。所以令 \(f_{i,j,p,q}\) 表示前 \(i+j\) 个人有 \(i\) 个男孩和 \(j\) 个女孩，所有后缀中男孩最多比女孩多 \(p\) 个，女孩最多比男孩多 \(q\) 个的方案数，转移直接枚举下一个位置是男孩还是女孩。
P2592 [ZJOI2008] 生日聚会
发布时间 2023-09-06 05:49:53作者: 御坂夏铃
一个一个填过去，显然对之后有影响的是当前的后缀。所以令 \(f_{i,j,p,q}\) 表示前 \(i+j\) 个人有 \(i\) 个男孩和 \(j\) 个女孩，所有后缀中男孩最多比女孩多 \(p\) 个，女孩最多比男孩多 \(q\) 个的方案数，转移直接枚举下一个位置是男孩还是女孩。