Oj.Nbdp.Net
初赛题库
问题
状态
排名
团队
题解
课程
Login
问题 6118 --菜单设计
6118: 菜单设计
警告!
题目
状态
题解
题目描述
小爱作为餐厅经理,他需要从 $n$ 道备选菜肴中,选出 $m$ 道菜品作为餐厅新一季度的正式菜单。当然,正式菜单中菜品的先后品尝顺序也会影响顾客的感受。 已知第 $i$ 道备选菜肴的美味值为 $x_i$,但有额外 $p$ 条菜品搭配建议,第 $i$ 条建议包含三个参数 $a_i$ 、$b_i$ 和 $c_i$,表示顾客在品尝完第 $a_i$ 道菜肴后,下一道直接品尝第 $b_i$ 道菜肴,会有额外 $c_i$ 点美味值。 问作为餐厅经理的小爱如何选择并设计安排菜肴及上菜顺序,才能使顾客品尝后的美味值最大。
输入
输入第一行,两个正整数$n,m$ 输入第二行,$n$个正整数,$x_1,...,x_n$ 输入第三行,一个正整数,$p$ 接下来$p$行,每行$3$个正整数,分别表示第$i$条建议的三个参数$a_i,b_i,c_i$
输出
输出一个正整数,表示所选菜单能获得的最大美味值。
样例输入输出
输入#1
复制
4 3 2 5 1 3 2 2 1 6 4 3 1
输出#1
复制
16
提示
+ 对于 $50\%$ 数据,$1 \leq m \leq n \leq 8$; + 对于 $100\%$ 数据,$1\leq m \leq n \leq 18$; $0\leq x_i,c_i \leq 10^9 ,1 \leq a_i,b_i \leq n$ ,$1\leq p \leq n \times (n-1)$ 。 数据保证没有两条菜品建议的$a_i$和$b_i$完全相同样 例1说明:按第2道、第1道、第4道备选菜肴的顺序组成正式菜单 获得 2+5+3=10 点美味值,外加第2道后接第1道备选菜肴所带来的 6 点额外美味值 故最大美味值为 16
发表题解
序号
标题
作者
发表时间
费用
订购数
操作
题目信息
提交
难度
普及+/提高-
标签
状态压缩
点击显示
if ($pr_flag) { ?>
递交数
1
已通过
1
} ;?>
通过率
100%
时间限制
1 秒
内存限制
256 MB
来源
YACS2022年11月月赛乙组
收藏
标签云
模拟
数学与数论
动态规划
贪心
字符串
排序
枚举
数组与串
深搜
高精度
循环结构
递推
递归
二分三分
宽搜
背包
质数
线段树
分治
N进制
图论
队列
最短路
堆
树
并查集
栈
状态压缩
分支结构
几何
博弈论
生成树
顺序结构
离散化
hash表
位运算
单调队列
树状数组
KMP
字典树
二分图
数学期望
AC自动机
树链剖分
差分约束
数位动态规划
函数与过程
网络流
单调栈
前缀和