#1701. 卡牌游戏

    ID: 1701 传统题 1000ms 256MiB 尝试: 0 已通过: 0 难度: NOI/NOI+/CTS 上传者: 标签>CTT赛事:contest1049来源:qoj.ac数据:公开样例动态规划枚举

卡牌游戏

卡牌游戏

题目描述

标题: 卡牌游戏 - Problem - QOJ.ac

Statistics

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。

输入格式

(见题面原文)

输出格式

(见题面原文)

数据范围

(见题面原文)

样例

样例 1

5 10 1 1
3 2 1 4 5
26 18

样例 2

10 9999 1 1
93 120 538 410 1 248 100 11 45 14
72490 231470