P1181 - 旅行商的背包

内存限制：128 MB 时间限制：1.000 S 标准输入输出

题目类型：传统评测方式：文本比较上传者：

提交：4 通过：3

小S坚信任何问题都可以在多项式时间内解决，于是他准备亲自去当一回旅行商。在出发之前，他购进了
一些物品。这些物品共有n种，第i种体积为Vi,价值为Wi,共有Di件。他的背包体积是C.怎样装
才能获得尽量多的收益呢？作为一名大神犇，他轻而易举的解决了这个问题。
然而，就在他出发前，他又收到了一批奇货。这些货共有m件，第i件的价值Yi与分配的体积Xi之间
的关系为：Yi=ai*(Xi)^2+bi*Xi+ci.这是件好事，但小S却不知道怎么处理了，于是他找到了一位超级
神犇（也就是你），请你帮他解决这个问题。

第一行三个数 n,m,C,如题中所述；
以下n行，每行有三个数Vi,Wi,Di,如题中所述；
以下m行，行有三个数ai,bi,ci,如题中所述。

仅一行，为最大的价值。

样例解释

前两种物品全部选走，最后一个奇货分给 44 的体积，收益为2×3+4×1+(−1)×16+8×4+(−16)=10。

限制与约定

对于 100% 的数据，1≤n≤10^4，1≤m≤5，1≤C≤10^4，1≤Wi,Vi,Di≤1000，−1000≤ai,bi,ci≤1000。

动态规划---混合背包

1181: 旅行商的背包

题目描述

输入格式

输出格式

输入样例复制

输出样例复制

数据范围与提示

分类标签