【JSOI2009】火星藏宝图

Source and Judge

JSOI2009
luogu4056

Record

2h

Analysis

请先思考后再展开

首先权值都都是正数,那么显然如果在一列路径上多一个点一定更优,所以每一列只会从最底下的那个转移
然后这样就能nm做了,卡卡常可以过
但这个式子显然是可以斜率优化的
$f(i)=f(j)-(x-pos_j)^2-(i-j)^2+w_i$
$f(j)-pos_j^2-2xpos-j^2=i(-2j)+(f(i)-w_i+i^2+x^2)$
最小化截距,然后i还是单调的,那么每行维护一个斜率单降凸壳即可,复杂度m方

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