Mayflyyh
Mayflyyh
MayFlyyh's Blog

分数规划
文章归档

POJ 2976 Dropping tests

给定n个二元组(a,b),扔掉k个二元组,使得剩下的a元素之和与b元素之和的比率最大。题目求的是 max(∑a[i] * x[i] / (b[i] * x[i])) 其中a,b都是一一对应的。 x[i]取0,1 并且 ∑x[i] = n - k。 看到除法,应该是分数规划吧。每次二分以后计算出一串数字对答案的贡…

   80   2018-07-16 去围观