BZOJ 1560: [JSOI2009]火星藏宝图

正文索引 [隐藏]

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=1560

Description

Input

Output

Sample Input

4 10
1 1 20
10 10 10
3 5 60
5 3 30

Sample Output

-4

HINT

题解

首先我们明确一点,从 (0,0) 移动到 (x,y) ,假定 x1+x2=x && y1+y2=y 。如果直接从(0,0)移动到(x,y),那么花费为x^2+y^2=x1^2+x2^2+2x1x2+y1^2+y2^2+2y1y2 > x1^2+y1^2+x2^2+y2^2 ,所以同样位置的移动,中继点越多花费越少。
那么很明显,我们要尽量多走一些点。
我们把点全部记录,并且按照行优先列其次的顺序排序,这样保证顺序做的时候与行。
然后,我们记F[j]为1~当前行,第j列最下面的岛屿的最优值。 O(M)转移,所以总的复杂度是O(MN)
不知道为什么,别人快得飞起,我却要开读入挂才能过。

代码