P3643 [APIO2016]划艇

· · 题解

题面传送门。

题意简述：给出序列 a_i,b_i，求出有多少序列 c_i 满足 c_i=-1 或 c_i\in[a_i,b_i]，同时非 -1 的部分单调递增。

本文选自 DP 大锅乱炖 例题 IX.。

直到做到这题我才意识到我的 DP 水平有多菜。

注意到值域过大，于是对区间进行离散化，设离散化后的端点分别为 p_1,p_2,\cdots,p_c。注意要将 [a_i,b_i] 变成 [a_i,b_i+1)，即将 b_i 加 1，方便计算答案。

接下来考虑 DP：设 f_{i,j} 表示第 i 个学校派出划艇数量在 L_j=[p_j,p_{j+1}) 之间时的方案数。

错误思路：f_{i,j}=\begin{cases}\sum_{pos=1}^{i-1}\sum_{k=1}^{j-1}f_{pos,k}\times (p_{j+1}-p_j)&[p_j,p_{j+1})\subseteq[a_i,b_i)\\0&\mathrm{otherwise}\end{cases}。错误原因：I. 没有考虑边界条件 & 枚举下界。II. 没有考虑在同一区间内也合法的情况。

边界条件就是 f_{i,0}=1，并且注意 pos,k 的枚举下界应为 0。

考虑在同一区间内合法的情况：不妨枚举最右端的不在区间 j 的位置 pos，那么剩下来 i-pos 个位置。假设当中有 m 个位置满足可以落在区间 j 上，那么方案数就相当于从 m-1 个 -1 和 L_j 个数 p_j,p_j+1,\cdots,p_{j+1}-1 中选出 m 个数（因为位置 i 必须选所以是 m-1 而不是 m；-1 相当于不选），即 \binom{m+L_j-1}{m}。

综上所述，更新后的转移方程应为 f_{i,j}=\begin{cases}\sum_{pos=0}^{i-1}\sum_{k=0}^{j-1}f_{pos,k}\times\binom{m+L_j-1}{m}&[p_j,p_{j+1})\subseteq[a_i,b_i)\\0&\mathrm{otherwise}\end{cases}。注意到后面的组合数可以 \mathcal{O}(1) 递推（\binom{m+L_j}{m+1}=\binom{m+L_j-1}{m}\times\frac{m+L_j}{m+1}），那么使用前缀和优化（因为 m 与枚举的 k 无关，所以记 s_{i,j}=\sum_{k=0}^j f_{i,k}，则上面那一坨可以写成 \sum_{pos=0}^{i-1}s_{pos,j-1}\times\binom{m+L_j-1}{m}）+ 倒序枚举 pos（实时更新 m 与组合数）即可 \mathcal{O}(n^3) 计算。

代码放在了 cnblogs 里面。