P9129

· · 题解

P9129 [USACO23FEB] Piling Papers G

转送门

相比其他dp题目，这题的dp方式我感觉比较新颖。

首先为了满足区间 [A,B] 的限制，我们可以直接前缀和用小于等于 B 的答案减去小于等于 A-1 的答案。

题面是要把 a_i 一个一个的插入到当前的串中，所以我们就一样的dp。为了满足小于等于 B 的限制，就设 f_{i,l,r,0/1/2} 表示现在考虑到第 i 个数，在串的长度是 r-l+1 ，在 B 的第 l 位到第 r 位中是小于/等于/大于。

转移就和一般的区间 dp 一样。

重点：状态设计。