#PQJ1191x6174. QOJ 1191_6174
QOJ 1191_6174
具有连续时间段和变化收益的任务安排问题可描述如下。
给定 𝑛 个任务的集合 𝐴 。 在上午完成的任务必须按照给定任务序列 𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑛 的顺序依次完成;在下午完成的任务必须按照给定任务序列 𝑦 1 , 𝑦 2 , ⋯ , 𝑦 𝑚 的顺序依次完成。 完成任务所获得的收益在不同时间段有所不同。在上午完成的任务序列 𝑥 𝑖 中的各项任务可获得相应收益 𝑎 𝑖 ,而在下午完成的任务序列 𝑦 𝑖 中的各项任务可获得相应收益 𝑏 𝑖 。 每个任务可以在上午完成,也可以在下午完成,但最多只能完成1次。
设 1 ≤ 𝑙 𝑎 + 1 ≤ 𝑟 𝑎 ≤ 𝑛 ,且 1 ≤ 𝑙 𝑏 + 1 ≤ 𝑟 𝑏 ≤ 𝑛 , 则 [ 𝑙 𝑎 , 𝑟 𝑎 ] 和 [ 𝑙 𝑏 , 𝑟 𝑏 ] 分别是上午和下午完成的连续任务区间。当 { 𝑥 𝑙 𝑎 , 𝑥 𝑙 𝑎 + 1 , ⋯ , 𝑥 𝑟 𝑎 } ∩ { 𝑦 𝑙 𝑏 , 𝑦 𝑙 𝑏 + 1 , ⋯ , 𝑦 𝑟 𝑏 }
∅ 时,称这两个连续任务区间不重叠,即这两个连续任务区间中的任务均不相同。此时,这两个连续任务区间所获得的总收益为:
∑ 𝑖
𝑙 𝑎 𝑟 𝑎 𝑎 𝑖 + ∑ 𝑖
𝑙 𝑏 𝑟 𝑏 𝑏 𝑖
最佳收益问题:对于给定的上午和下午完成的任务序列,在所有不重叠的连续任务区间对中,计算能获得的最大收益。上午和下午完成的连续任务区间均可为空,此时相应的任务区间中没有任务。
输入格式
第一行中有两个正整数 𝑛 和 𝑚 ,分别表示上午和下午完成的任务序列的长度。
第二行中有 𝑛 个整数,表示上午完成的任务序列 𝑥 1 , 𝑥 2 , ⋯ , 𝑥 𝑛 。
第三行中有 𝑛 个整数,表示上午完成的任务序列所相应的收益 𝑎 1 , 𝑎 2 , ⋯ , 𝑎 𝑛 。
第四行中有 𝑚 个整数,表示下午完成的任务序列 𝑦 1 , 𝑦 2 , ⋯ , 𝑦 𝑚 。
第五行中有 𝑚 个整数,表示下午完成的任务序列所相应的收益 𝑏 1 , 𝑏 2 , ⋯ , 𝑏 𝑚 。
输出格式
输出一行一个整数,表示答案。
样例数据 样例输入 8 5 12 10 2 1 6 7 4 8 1 9 2 8 2 10 9 10 6 9 7 8 3 7 7 8 3 3 样例输出 58 子任务
测试数据中 40 % 的数据满足 𝑛 , 𝑚 ≤ 10 000
测试数据中 100 % 的数据满足 1 ≤ 𝑛 , 𝑚 ≤ 500 000 , 1 ≤ 𝑎 𝑖 , 𝑏 𝑖 ≤ 10 9 , 1 ≤ 𝑥 𝑖 , 𝑦 𝑖 ≤ 𝑛 + 𝑚 。