Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 5400 --购买礼物
5400: 购买礼物
警告!
题目
状态
题解
题目描述
商店里总共有 $n$ 个礼物,编号分别为 $1$ 到 $n$。假设$P_i 、V_i$ 分别表示第 $i$ 件物品的价格和小明女朋友的喜爱程度。有一些礼品是有特殊含义的,小明必须给他的女朋友买。 小明现在手上有两张信用卡,而且这两张信用卡只能分开使用。即假设当第一张卡中有 $3$ 元,第二张卡中有 $2$ 元时,小明不能用这两张卡购买 $5$ 元的礼物。 商店老板准备免费赠送小明一个礼物。问如何购买礼物才能使他女朋友对礼物的喜爱值之和最大。
输入
第一行包含三个整数,$V1、V2$ 和 $n$,分别表示两张信用卡的额度和礼物的个数。 接下来 $n$ 行,每行三个整数,$P_i、V_i、S_i$ 分别表示礼物的价格、喜爱程度以及是否必须购买,$S_i=1$ 表示该礼物必须购买,$S_i=0$ 表示不一定要购买。
输出
一行一个整数,表示小明女朋友对礼物的喜爱程度。若小明不能将所有必须购买的礼物购买到,那么就输出 `-1`。
样例输入输出
输入#1
复制
3 2 4 3 10 1 2 10 0 5 100 0 5 80 0
输出#1
复制
120
输入#2
复制
3 2 4 3 10 1 2 10 0 5 100 0 5 80 1
输出#2
复制
100
提示
对于 $20\%$ 的数据,$1 \leq n \leq 50$。 对于 $100\%$ 的数据,$1 \leq V1 \leq 500$,$1 \leq V2 \leq 50$,$1 \leq n \leq 300$。
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
未评定
标签
点击显示
if ($pr_flag) { ?>
递交数
2
已通过
2
} ;?>
通过率
100%
时间限制
1 秒
内存限制
128 MB
来源
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和