【IOI2016】外星人

题意:给定一个\(m\times m\)的网格和\(n\)个其中的关键点,用不超过\(k\)个中心在网格主对角线上的正方形覆盖全部的关键点使得所有正方形的覆盖面积的并最小。

 

显然可以dp。首先对于一个点,如果存在另一个点\(x\)坐标更小而\(y\)坐标更大那么显然这个点可以删掉。那么令\(f_{i,j}\)表示用\(j\)个正方形覆盖了前\(i\)个点的最小面积,转移很显然,并且可以使用斜率优化。

考虑\(f_i\)是一个凸函数。每多一个正方形减少的权值只有可能更少。

那么就可以二分斜率直到切点为\(k\)即可,也就是二分每选择一个正方形需要额外付出的权值,直到最优解为选择\(k\)个。

说点什么

2 评论 在 "【IOI2016】外星人"

提醒
排序:   最新 | 最旧 | 得票最多
成员

你是zz吧,深夜发博客

成员

深夜发博客伤身

wpDiscuz