menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[wqs二分+决策单调性]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告我再来水一遍这道题……之前已经用了wqs二分去掉了一维状态,这时候DP的状态数,转移...
apps POJ
local_offer 查看标签
comment 0 条评论
阅读全文
[wqs二分+DP]POJ1160【Post Office】题解
题目概述有 $n$ 个村庄,现在要建 $m$ 个邮局,一种方案的代价是每个村庄到最近的邮局的距离之和。解题报告显然是 $O(n^2m)$ DP吧?数据小的可怜,这样就可以过了……不过有一种更好的...
apps POJ
local_offer 查看标签
comment 0 条评论
阅读全文
[最大密度子图]POJ3155【Hard Life】题解
题目概述有 $n$ 个员工 $m$ 条矛盾,现在要炒若干个员工的鱿鱼,一组方案的权值是矛盾数与员工数的比值。求最大比值的方案。解题报告最大密度子图模板题。双倍经验BZOJ1312,没权限号就在P...
keyboard_arrow_up