首页 > 其他分享 >P3643 [APIO2016] 划艇

P3643 [APIO2016] 划艇

时间:2023-11-14 18:36:12浏览次数:48  
标签:limits 个数 sum APIO2016 P3643 划艇 区间 cases dp

[APIO2016] 划艇 - 洛谷

题目详情 - [Apio2016] 赛艇 - BZOJ by HydroOJ

  • 看着个题目以为是变换考虑方向,但想了半天完全没有思路

  • 先考虑暴力。设 \(dp_{i,j}\) 表示前 \(i\) 个数,第 \(i\) 个数强制选,值为 \(j\) 的方案数

  • 容易得到转移方程:

    \[dp_{i,j}= \begin{cases} \sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^{j-1}dp_{k,l} & j\in[l_i,r_i] \\ 0 &otherwise \end{cases} \]

  • 这么做显然不行,因为值域太大了,状态根本列不下。考虑离散化。

  • 我们先把闭区间变成左闭右开区间后离散化,记 \([b_i,b_{i+1})\) 为第 \(i\) 个区间,考虑改变 \(dp\) 状态的定义

  • 设 \(dp_{i,j}\) 表示前 \(i\) 个数,第 \(i\) 个强制选,值在第 \(j\) 个区间内的方案数。转移时我们枚举第一个值在第 \(j-1\) 区间内的位置 \(k\) 即可转移。

  • 如果你这么想你就太 naive 了!

  • 我们发现我们完全没有考虑 \((k,i]\) 区间内的填数情况,这些区间里的数要么是在区间 \(j\) 中要么没有选,我们要考虑计算这里面的方案数。

  • 引理:从 \([x,x+L-1]\) 这些数中选 \(n\) 个数,使得构造的序列非 \(0\) 位单增的方案数为 \(\binom{L+n}{n}\)

    证明:如果没有选择非 \(0\) 位的条件的话方案数显然为 \(\binom{L}{n}\),即从\(1,2,3,\cdots,L\) 中选 \(n\) 位即可。现在新增了选 \(0\) 的条件,我们不妨沿用插板法的思路,把原序列前添加上 \(n\) 位 \(0\),此时如果选择了第 \(i\) 个 \(0\),则等价于在第 \(i\) 位后面插入一个 \(0\) 。

  • 有了这个定理,我们就可以列出转移方程:

    \[dp_{i,j}= \begin{cases} \sum\limits_{k=0}^{i-1}\sum\limits_{l=1}^{j-1} \binom{L+m-1}{m}\times dp_{k,l} & j\in[l'_i,r'_i] \\ 0 &otherwise \end{cases} \]

    其中 \(L=b_{j+1}-b_j\),\(m\) 表示 \((k,i]\) 中包含第 \(j\) 个区间的区间个数。组合数上标 \(-1\) 是因为我们强制第 \(i\) 位选。

  • 这么做还不太够,因为暴力转移这个式子是 \(O(n^4)\) 的,发现我们可以用前缀和优化,最终可以做到 \(O(n^3)\)

标签:limits,个数,sum,APIO2016,P3643,划艇,区间,cases,dp
From: https://www.cnblogs.com/fox-konata/p/17832253.html

相关文章

  • P3643 [APIO2016] 划艇
    题意给你两个序列\(a,b\),求严格递增的序列\(c\)的个数,满足:\(\foralli,c_i\in[a_i,b_i]\)。特别的,如果\(c_i=0\)则无视当前这个\(c_i\)。Solution好困难的dp,耗我......