COCI '15 Contest 6 #4 Parovi 动态规划递归思路求解咨询

首先先明确题意的准确表述：我们需要统计满足以下两个条件的二元配对集合数目：

1. 1必须出现在至少一个配对中
2. 对每个2 ≤ k ≤ N，都存在至少一个配对(a,b)使得a < k < b

状态设计 #

你之前采用一维dp[i]的定义粒度过粗，很容易出现重复计数或者漏算的问题，这里推荐用区间DP的二维状态：
定义dp[l][r]为满足以下条件的配对集合数目：

• 所有配对的端点都在区间[l, r]内
• 所有满足l < k < r的整数k，都存在配对(a,b)使得a < k < b
• l和r都至少出现在一个配对中

我们要求的最终答案就是dp[1][N]。

转移逻辑 #

我们按区间长度从小到大计算所有dp[l][r]：

1. 预处理2的幂次数组pow2，其中pow2[x]表示2的x次方对模数取模的结果，因为最多有C(N,2)个可选配对，预处理到C(N,2)即可。
2. 当区间长度为2（即r = l + 1）时，dp[l][r] = 1：唯一合法的集合就是仅包含配对(l, r)的集合。
3. 当区间长度大于2时，分两类统计避免重复：
   • 第一类：集合中包含配对(l, r)：只要存在(l, r)，就天然满足所有中间k被覆盖的要求，剩下的C(r-l+1, 2) - 1个配对可以任意选或不选，这部分的数目为pow2[ (r - l + 1) * (r - l) / 2 - 1 ]
   • 第二类：集合中不包含配对(l, r)：此时我们枚举和l配对的最大右端点m，为了覆盖k = l + 1，m必须满足m ≥ l + 2。此时[l, m]区间的合法数目为dp[l][m]，而[m, r]区间内的配对可以任意选择（因为我们枚举的是最大的m，不会和其他情况重复），这部分的转移为sum_{m = l + 2}^{r - 1} dp[l][m] * pow2[ (r - m + 1) * (r - m) / 2 ]

最终dp[l][r]就是两部分相加的结果，按区间长度从小到大递推就能得到最终答案。

小值验证 #

• N=2时，dp[1][2] = 1，符合预期
• N=3时，dp[1][3] = pow2[3*2/2 - 1] + 0 = pow2[2] =4，和手动计算结果一致
• N=4时，dp[1][4] = pow2[4*3/2 -1] + dp[1][3] * pow2[2*1/2] = pow2[5] + 4*2 = 32 + 8 =40，和手动计算结果一致

内容的提问来源于stack exchange，提问作者Bully Maguire