【CF720D】Slalom

Source and Judge

CF720D

Record

30min

Analysis

请先思考后再展开

显然是dp,每个位置存储到这里的方案数
然后考虑怎么去重
给出一个例子:每次向右更新,如果(x+1,y)上方存在某个矩形的边缘,则向上更新

考虑加速,发现dp中前面的信息是没用的,扫描线,每次询问区间和然后单点修改即可

本文基于 知识共享署名-相同方式共享 4.0 国际许可协议发布
本文地址:http://zory.ink/posts/bb3b.html
转载请注明出处,谢谢!