#PQJ389x3268. QOJ 389_3268

    ID: 2941 传统题 1000ms 512MiB 尝试: 0 已通过: 0 难度: 省选/NOI- 上传者: 标签>来源:qoj.ac章节练习数据:双算对拍权威答案来源:省选赛事:六省联合省选2017动态规划

QOJ 389_3268

2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试寿司餐厅(sushi) 寿司餐厅(sushi) 【问题描述】 Kiana 最近喜欢到一家非常美味的寿司餐厅用餐。 每天晚上,这家餐厅都会按顺序提供n 种寿司,第i 种寿司有一个代号ai 和美味 度di,i,不同种类的寿司有可能使用相同的代号。每种寿司的份数都是无限的,Kiana 也可以无限次取寿司来吃,但每种寿司每次只能取一份,且每次取走的寿司必须是按餐 厅提供寿司的顺序连续的一段,即Kiana 可以一次取走第1, 2 种寿司各一份,也可以 一次取走第2, 3 种寿司各一份,但不可以一次取走第1, 3 种寿司。 由于餐厅提供的寿司种类繁多,而不同种类的寿司之间相互会有影响:三文鱼寿司 和鱿鱼寿司一起吃或许会很棒,但和水果寿司一起吃就可能会肚子痛。因此,Kiana 定 义了一个综合美味度di,j(i < j),表示在一次取的寿司中,如果包含了餐厅提供的从第i 份到第j 份的所有寿司,吃掉这次取的所有寿司后将获得的额外美味度。由于取寿司 需要花费一些时间,所以我们认为分两次取来的寿司之间相互不会影响。注意在吃一次 取的寿司时,不止一个综合美味度会被累加,比如若Kiana 一次取走了第1, 2, 3 种寿 司各一份,除了d1,3 以外,d1,2, d2,3 也会被累加进总美味度中。 神奇的是,Kiana 的美食评判标准是有记忆性的,无论是单种寿司的美味度,还是 多种寿司组合起来的综合美味度,在计入Kiana 的总美味度时都只会被累加一次。比 如,若Kiana 某一次取走了第1, 2 种寿司各一份,另一次取走了第2, 3 种寿司各一份, 那么这两次取寿司的总美味度为d1,1 + d2,2 + d3,3 + d1,2 + d2,3,其中d2,2 只会计算一次。 奇怪的是,这家寿司餐厅的收费标准很不同寻常。具体来说,如果Kiana 一共吃 过了c 种代号为x 的寿司,则她需要为这些寿司付出mx2 + cx 元钱,其中m 是餐厅给 出的一个常数。 现在Kiana 想知道,在这家餐厅吃寿司,自己能获得的总美味度(包括所有吃掉 的单种寿司的美味度和所有被累加的综合美味度)减去花费的总钱数的最大值是多少。 由于她不会算,所以希望由你告诉她。 【输入格式】 从文件sushi.in 中读入数据。 第一行包含两个正整数n, m,分别表示这家餐厅提供的寿司总数和计算寿司价格中 使用的常数。 第二行包含n 个正整数,其中第k 个数ak 表示第k 份寿司的代号。 接下来n 行,第i 行包含n −i + 1 个整数,其中第j 个数di,i+ j−1 表示吃掉寿司能 获得的相应的美味度,具体含义见问题描述。 第10 页 共14 页

2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试寿司餐厅(sushi) 【输出格式】 输出到文件sushi.out 中。 输出共一行包含一个正整数,表示Kiana 能获得的总美味度减去花费的总钱数的 最大值。 【样例1 输入】 3 1 2 3 2 5 -10 15 -10 15 15 【样例1 输出】 12 【样例1 说明】 在这组样例中,餐厅一共提供了3 份寿司,它们的代号依次为a1 = 2,a2 = 3, a3 = 2,计算价格时的常数m = 1。在保证每次取寿司都能获得新的美味度的前提下, Kiana 一共有14 种不同的吃寿司方案: 1.Kiana 一个寿司也不吃,这样她获得的总美味度和花费的总钱数都是0,两者相 减也是0; 2.Kiana 只取1 次寿司,且只取第1 个寿司,即她取寿司的情况为{[1, 1]},这样获 得的总美味度为5,花费的总钱数为1 ∗22 + 1 ∗2 = 6,两者相减为−1; 3.Kiana 只取1 次寿司,且只取第2 个寿司,即她取寿司的情况为{[2, 2]},这样获 得的总美味度为−10,花费的总钱数为1 ∗32 + 1 ∗3 = 12,两者相减为−22; 4.Kiana 只取1 次寿司,且只取第3 个寿司,即她取寿司的情况为{[3, 3]},这样获 得的总美味度为15,花费的总钱数为1 ∗22 + 1 ∗2 = 6,两者相减为9; 5.Kiana 只取1 次寿司,且取第1, 2 个寿司,即她取寿司的情况为{[1, 2]},这样获得 的总美味度为5+(−10)+(−10) = −15,花费的总钱数为(1∗22+1∗2)+(1∗32+1∗3) = 18, 两者相减为−33; 6.Kiana 只取1 次寿司,且取第2, 3 个寿司,即她取寿司的情况为{[2, 3]},这样获得 的总美味度为(−10)+15+15 = 20,花费的总钱数为(1∗22 +1∗2)+(1∗32 +1∗3) = 18, 两者相减为2; 7.Kiana 只取1 次寿司,且取第1, 2, 3 个寿司,即她取寿司的情况为{[1, 3]}, 这样获得的总美味度为5 + (−10) + 15 + (−10) + 15 + 15 = 30,花费的总钱数为 第11 页 共14 页

2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试寿司餐厅(sushi) (1 ∗22 + 2 ∗2) + (1 ∗32 + 1 ∗3) = 20,两者相减为10。 8.Kiana 取2 次寿司,第一次取第1 个寿司,第二次取第2 个寿司,即她取寿 司的情况为{[1, 1], [2, 2]},这样获得的总美味度为5 + (−10) = −5,花费的总钱数为 (1 ∗22 + 1 ∗2) + (1 ∗32 + 1 ∗3) = 18,两者相减为−23; 9.Kiana 取2 次寿司,第一次取第1 个寿司,第二次取第3 个寿司,即她取寿司的情 况为{[1, 1], [3, 3]},这样获得的总美味度为5+15 = 20,花费的总钱数为1∗22 +2∗2 = 8, 两者相减为12; 10.Kiana 取2 次寿司,第一次取第2 个寿司,第二次取第3 个寿司,即她取寿 司的情况为{[2, 2], [3, 3]},这样获得的总美味度为(−10) + 15 = 5,花费的总钱数为 (1 ∗22 + 1 ∗2) + (1 ∗32 + 1 ∗3) = 18,两者相减为−13; 11.Kiana 取2 次寿司,第一次取第1, 2 个寿司,第二次取第2 个寿司,即她取寿 司的情况为{[1, 2], [3, 3]},这样获得的总美味度为5 + (−10) + (−10) + 15 = 0,花费的 总钱数为(1 ∗22 + 2 ∗2) + (1 ∗32 + 1 ∗3) = 20,两者相减为−20; 12.Kiana 取2 次寿司,第一次取第1 个寿司,第二次取第2, 3 个寿司,即她取寿 司的情况为{[1, 1], [2, 3]},这样获得的总美味度为5 + (−10) + 15 + 15 = 25,花费的总 钱数为(1 ∗22 + 2 ∗2) + (1 ∗32 + 1 ∗3) = 20,两者相减为5; 13.Kiana 取2 次寿司,第一次取第1, 2 个寿司,第二次取第2, 3 个寿司,即她取 寿司的情况为{[1, 2], [2, 3]},这样获得的总美味度为5 + (−10) + 15 + (−10) + 15 = 15, 花费的总钱数为(1 ∗22 + 2 ∗2) + (1 ∗32 + 1 ∗3) = 20,两者相减为−5; 14.Kiana 取3 次寿司,第一次取第1 个寿司,第二次取第2 个寿司,第三次取第3 个 寿司,即她取寿司的情况为{[1, 1], [2, 2], [3, 3]},这样获得的总美味度为5+(−10)+15 = 10, 花费的总钱数为(1 ∗22 + 2 ∗2) + (1 ∗32 + 1 ∗3) = 20,两者相减为−10。 所以Kiana 会选择方案9,这时她获得的总美味度减去花费的总钱数的值最大为 12。 【样例2 输入】 5 0 1 4 1 3 4 50 99 8 -39 30 68 27 -75 -32 70 24 72 -10 81 -95 【样例2 输出】 381 第12 页 共14 页

2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试寿司餐厅(sushi) 【样例3 输入】 10 1 5 5 4 4 1 2 5 1 5 3 83 91 72 29 22 -5 57 -14 -36 -3 -11 34 45 96 32 73 -1 0 29 -48 68 44 -5 96 66 17 74 88 47 69 -9 2 25 -49 86 -9 -77 62 -10 -30 2 40 95 -74 46 49 -52 2 -51 -55 50 -44 72 22 -68 【样例3 输出】 1223 【子任务】 对于所有数据,保证−500 ≤di,j ≤500。 数据的一些特殊约定如下表: 第13 页 共14 页

2017 年全国青少年信息学奥林匹克竞赛山西省代表队选拔 第二试寿司餐厅(sushi) 测试点编号 n ai m 备注 1 ≤2 ≤30 = 0 无 2 = 1 3 ≤3 = 0 4 = 1 5 ≤5 = 0 6 = 1 7 ≤10 = 0 所有的ai 相同 8 = 1 无 9 ≤15 = 0 所有的ai 相同 10 = 1 无 11 ≤30 ≤1000 = 0 所有的ai 相同 12 ≤30 = 0 13 ≤1000 = 0 无 14 = 1 15 ≤50 = 0 所有的ai 相同 16 ≤30 = 0 17 ≤1000 = 0 无 18 = 1 19 ≤100 = 0 无 20 = 1 第14 页 共14 页