Cruiying

分数规划

2-sat(1) BSGS(2) dfs(2) dp(63) dp + 线段树(1) floyd(3) Hash(1) KM算法(1) Kruskal重构树(2) LCA(6) manachar(2) Mendix(4) tarjan(1) 中位数(1) 主席树(2) 二分(3) 前缀和优化dp(2) 单调栈(6) 单调队列(1) 单调队列优化dp(1) 博弈(2) 后缀数组(15) 字典树(1) 差分约束系统(1) 并查集(4) 异或(2) 思维(2) 思维题(4) 扩展欧几里得算法(1) 拉格朗日插值(2) 数论(8) 未归档(15) 构造(1) 枚举(1) 模拟(3) 模板(1) 水题(4) 矩阵加速(2) 线段树(3) 网络流(2) 莫比乌斯反演(2) 莫队(4) 蓝桥杯(1) 规律(2) 贪心(2) 输入输出(1) 题解(1)

/ 注册

全部文章 / 分数规划（共3篇）

小咪买东西分数规划

链接：https://ac.nowcoder.com/acm/problem/14662 来源：牛客网小咪是一个土豪手办狂魔，这次他去了一家店，发现了好多好多（n个）手办，但他是一个很怪的人，每次只想买k个手办，而且他要让他花的每一分钱都物超所值，即：买下来的东西的总价值/总花费=max。请你来...

2019-04-18

0 539

luoguP4377 01分数规划背包dp

emmm……看到题面“总才艺值与总体重的比值最大”，那么这个就是01分数规划问题了。现在详细讲一讲如何解决这类问题。先看简单一点的题：有 n 个物品，有属性值 ai,bi要求选出至多 k 个物品，使得sum(ai) / sum(bi)尽可能大。我们要首先二分答案 x，若 sum(ai...

分数规划

2019-04-16

0 568

luoguP4377 01分数规划背包dp

emmm……看到题面“总才艺值与总体重的比值最大”，那么这个就是01分数规划问题了。现在详细讲一讲如何解决这类问题。先看简单一点的题：有 n 个物品，有属性值 ai,bi要求选出至多 k 个物品，使得sum(ai) / sum(bi)尽可能大。我们要首先二分答案 x，若 sum(ai...

2019-04-16

0 457