#PQJ1049x5100. QOJ 1049_5100
QOJ 1049_5100
标题: 卡牌游戏 - Problem - QOJ.ac
The problem was used in the following contests:
你的面前有 n 张卡牌,从左往右数第 i 张上面写着一个正整数 Ai。
你将会拿出其中的若干张,保持它们的相对顺序不变,形成一个新的卡牌序列。
不妨设这个新的卡牌序列有 m 张牌,第 i 张上写的数是 Bi。
定义这个卡牌序列的价值是:
∑i=1m−1⌊SLCM(Bi,Bi+1)⌋×LCM(Bi,Bi+1)
其中 LCM(x,y) 表示 x 和 y 的最小公倍数。
请最大化价值。
对于一些数据,你还需要解决如下问题:
增加禁用规则,如果第 i 张牌被禁用,你拿出的卡牌序列不可以包含它。
你想知道:对于 i=1...n,它被禁用后,你可以拿出的卡牌序列的价值最大是多少,设为 ansi。
为了减少输出量,你只需输出 ⨁i=1ni×ansi。
输入格式
第一行四个正整数 n,S,tp,id,前两个参数如上所示, tp=0/1 表示该数据的类型(详见输出格式), id 表示子任务编号。
第二行 n 个正整数 A1...An。
输出格式
- 若 tp=0,输出一行一个整数,表示无禁用规则的答案。
- 若 tp=1,输出一行两个整数,分别表示表示无禁用规则的答案和禁用规则下的 ⨁i=1ni×ansi。
样例数据
样例 1 输入
5 10 1 1
3 2 1 4 5
样例 1 输出
26 18
样例 2 输入
10 9999 1 1
93 120 538 410 1 248 100 11 45 14
样例 2 输出
72490 231470
数据范围与约定
子任务编号 分值 n≤ S≤ 特殊性质 1 5 103 105 无 2 5 104 3 10 105 3×105 Ai 在 [1,S] 中均匀随机 4 10 Ai≤100 5 10 105 tp=0 6 10 无 7 10 3×105 3×105 tp=0 8 10 无 9 15 5×105 5×105 tp=0 10 15 无
对于所有数据,1≤Ai≤109。