APIO(2016后)

1/?

APIO2016 划艇

请先思考后再展开

注意到值域大n小,考虑区间离散化
设dp(i,j,k)表示处理了前i个,最后一个选的人在第j个区间且目前该区间有k人选,没人选j=0
然后剩下就没什么了,但要注意不要像我一样一开始写满的复杂度,被卡成27,思考怎么让他不满就能过了
然后现在想想,应该插入a和b+1,这样可以把mx减小一半来着

$O(n^3)$,code

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