HBC20803[NOI2017]蔬菜题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案， 在蔬菜仓库中，共存放有 n 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各 方面因素，设计合理的销售方案，以获得最多的收益， 在计算销售蔬菜的收益时，每销售一个单位第 i 种蔬菜，就可以获得 ai 的收益， 特别地，由于政策鼓励商家进行多样化销售，第一次销售第 i 种蔬菜时，还会额外 得到 si 的额外收益， 在经营开始时，第 i 种蔬菜的

小 N 是蔬菜仓库的管理员，负责设计蔬菜的销售方案。 在蔬菜仓库中，共存放有 n 种蔬菜，小 N 需要根据不同蔬菜的特性，综合考虑各 方面因素，设计合理的销售方案，以获得最多的收益。 在计算销售蔬菜的收益时，每销售一个单位第 i 种蔬菜，就可以获得 ai 的收益。 特别地，由于政策鼓励商家进行多样化销售，第一次销售第 i 种蔬菜时，还会额外 得到 si 的额外收益。 在经营开始时，第 i 种蔬菜的库存为 ci 个单位。 然而，蔬菜的保鲜时间非常有限，一旦变质就不能进行销售，不过聪明的小 N 已 经计算出了每个单位蔬菜变质的时间：对于第 i 种蔬菜，存在保鲜值 xi，每天结束时会 有 xi 个单位的蔬菜变质，直到所有蔬菜都变质。（注意：每一单位蔬菜的变质时间是固 定的，不随销售发生变化） 形式化地：对于所有的满足条件 d × xi ≤ ci 的正整数 d ，有 xi 个单位的蔬菜将在 第 d 天结束时变质。 特别地，若 (d − 1) × xi ≤ ci < d × xi ，则有 ci − (d − 1) × xi 单位的蔬菜将在第 d 天 结束时变质。 注意，当 xi = 0 时，意味着这种蔬菜不会变质。 同时，每天销售的蔬菜总. 量. 也是有限的，最多不能超过 m 个单位。 现在，小 N 有 k 个问题，想请你帮忙算一算。每个问题的形式都是：对于已知的 pj，如果需要销售 pj 天，最多能获得多少收益？ 

标签： HBC20803[NOI2017]蔬菜题解