题目名称 749. 电子书狂热者
输入输出 zealot.in/out
难度等级
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试数据 10
题目来源 Gravatarcqw 于2012-04-06加入
开放分组 全部用户
提交状态
分类标签
分享题解
通过:4, 提交:23, 通过率:17.39%
Gravatardigital-T 100 0.557 s 0.62 MiB C++
Gravatarww944606393 100 0.558 s 0.62 MiB C++
Gravatarcstdio 100 1.777 s 0.59 MiB C++
Gravatarmildark 100 1.790 s 0.59 MiB C++
Gravatar艮山谦 60 5.422 s 0.52 MiB C++
Gravatar艮山谦 60 5.427 s 0.52 MiB C++
Gravatardigital-T 50 0.165 s 0.46 MiB C++
Gravatarfeng 50 3.057 s 3.53 MiB C++
Gravatarfeng 50 6.166 s 3.53 MiB C++
Gravatarmildark 40 1.747 s 0.53 MiB C++
本题关联比赛
20140423
关于 电子书狂热者 的近10条评论(全部评论)
回复 @digital-T :
谢谢神犇,你代码中的F我猜应该是记录的天数吧,具体细节有些不太理解的地方.这道题网上用原题搜索找不到解题报告(可能是我方法有问题吧),如果神犇有时间的话不知是否可以写篇题解点拨下蒟蒻,非常感谢
GravatarChenyao2333
2014-04-24 17:51 6楼
回复 @Chenyao2333 :
B套餐还是要按照天数算的,你举的例子的话如果用B套餐必须按那一整天算的
混用是可以的,只不过白白花了一些钱罢了,但可能比其他更优
Gravatardigital-T
2014-04-23 19:16 5楼
@cstdio 求解,愿闻其详
GravatarChenyao2333
2014-04-23 15:08 4楼
两个套餐可混用否,如果混用,比如某一天读5本书,已经用套餐A读了4本书,这时候用套餐B怎么算?
GravatarChenyao2333
2014-04-23 11:09 3楼
*&!*(%(!&(%*&@#*$^ sgm居然是sigma,哇擦!!!!!
已修改,简直直接少了一维!!
Gravatardigital-T
2014-04-23 11:03 2楼
神翻译啊神翻译,关键的几句话被一个0代替了。原本以为只是个稍微复杂的线性DP,但是在wa多次之后才发现是题错了。
题目错误已经改正,但是不保证完全正确(真的没耐心再看这道题了),做这题的话最好看原版题目SOJ-1695
Gravatarfeng
2013-03-18 16:31 1楼

749. 电子书狂热者

★   输入文件:zealot.in   输出文件:zealot.out   简单对比
时间限制:1 s   内存限制:128 MiB

【问题描述】

最低价值协会( ACM )是一个非营利性的组织,旨在帮助人们节省资源和金钱。现在, ACM 正在发展一种软件,帮助号称是电子书狂热者省钱。
电子书狂热者热衷于在线读书,有时他一天读的书超过 10 本,没人知道他一天休息多长时间,电子书不是免费的,事实上,他们并不便宜。通过下图( 2.5.1 ), ACM 能了解到狂热者读了多少本书。

第 1 天 第 2 天 第 3 天 第 4 天 第 5 天
1 1 5 1 1

图 2.5.1 所读的书

狂热者在第一天读了 1 本书,第三天读了 5 本书,通过图 2.5.2 , ACM 能知道读一本电子书的价格,不幸的是,价格并不是一成不变的。

第 1 天 第 3 天 第 5 天
5 1 2

图 2.5.2 每天的价格

在第 1 天和第 2 天每本电子书的价格为 5 ,到第三天每本书的价格变为 1 ,在第 5 天每本书价格又变为 2 ,因此狂热者需要为他读过的 9 本书付给电子书经营者的钱数为: 5×(1+1)+1×(5+1)+2×1=18 。
为了吸引更多的人来在线读书,电子书经营者推出了一些套餐,见下图 (2.5.3) 。

套餐 A1 A2
连续读的书本数 2 4
花费 6 7

图 2.5.3 菜单 A

这意味着如果狂热者选择套餐 A1 ,他连读两本书需付钱数为 6 ,如果选择套餐 A2 ,连读 4 本书需付钱数为 7 ,举例说明:如果他使用套餐 A1 为前两本书付费、用套餐 A2 为接下来的 4 本书付费,而剩下的 3 本书不使用任何套餐,那么所付总费用为: 6+7+1+1+2=17 。实际上,如果他使用套餐 A2 为前 4 本书付费,剩下的 5 本书不使用任何套餐,他将付的费用为: 7+1×3+1+2=13 。当然了,如果需要的话套餐可以多次使用,而且,如果需要,可以使用 “w 本书套餐 ” 为连续的 q 本书付费,其中 q(0 < q < w) 此外,电子书经营者还推出了另一类套餐,在这些套餐中,经营者关心的重点不在狂热者读了多少本书,而在于狂热者读了多少天书。请看下图 (2.5.4) :

套餐 B1 B2
连续读的天数 3 4
花费 9 12

图 2.5.4 菜单 B

这意味着,如果狂热者选择套餐 B1 ,他将为连续三天的读书(不管读了多少本)付费用为 9 ,如果选择套餐 B2 ,连续读 4 天要付的费用为 12 。举例说明:如果他用套餐 B2 为前 4 天付费,剩下的一天不使用任何套餐,他所需付的费用为: 12+2=14 ,同样的,套餐不限使用次数,并且可以使用 “w 天套餐 ” 为连续的 q 天阅读付费,其中q (0 < q < w)

【输入格式】
输入文件中有若干个测试数据,对于每一组测试数据,第一行只包含一个整数 n(0≤n≤1,000) ,表示狂热者所读的天数。

第二行包含 n 个非负整数 d 1 ,d 2 ,...,d n (∑ d i ≤10,000)

然后是一个整数n1表示有n1次价格变化 (0 < n1 ≤ 1,000)

c 1 p 1
c 2 p 2
...
c n1 p n1
(c 1 =1 , c1 < c2 < … < cn1 ≤ n, p1, p2… pn1 > 0)
这些数据表示在第 c i 天,读一本书的价格变为 pi (0 < i ≤ n1)

接着是一个整数n2,表示第一种套餐的数量 (0 ≤ n2 ≤ 1,000)

a 1 r 1
a 2 r 2
...
a n2 r n2

(0 < a1 < a2 < … < an2 ≤ 10,000, r1, r2… rn2 > 0)
这些数据表示狂热者可以为连续读的 a i (或小于 a i )本书付费用 r i ,

接着是一个整数n3,表示第二种套餐的数量 (0 ≤ n3 ≤ 1,000)

b 1 s 1
b 2 s 2
...
b n3 s n3
(0 < b1 < b2 < … < bn3 ≤ 1,000, s1, s2… sn3 > 0)
这些数据表示狂热者可以为连续读的 b i (或小于 b i )天付费用 s i ,

 输入数据以单独的一行包含一个 0 表示结束。
【输出格式】
对于每一个测试数据,输出仅有一行,即狂热者所需付的最小费用。
【输入样例】
输入文件名: zealot .in
5
1 1 5 1 1
3
1 5
3 1
5 2
2
2 6
4 7
2
3 9
4 12
0
输出文件名: zealot .out
12