UOJ Logo Universal Online Judge

UOJ

#811. 【UNR #7】璀璨宝石

附件下载 统计

有一款名为璀璨宝石(Splendor)的桌游,在重(zhòng)庆交通大学(ZJU)的 102B 宿舍中广受欢迎。小青鱼偶然间认识了 102B 的同学们,并本着“来都来了”的精神,一起玩起了这款桌游。大战了三天三夜之后,他突发奇想:如果稍微修改并简化下游戏规则,我们能找到这个游戏的最优解吗?

本题中的游戏规则与原桌游规则存在出入,请仔细读题。

游戏中有 n 张发展卡构成一个牌堆。和原桌游中一样,每张发展卡需要宝石才能购买。游戏一共有 5 种不同类型的宝石——白色、红色、绿色、蓝色和黑色。为了简单起见,我们用 A,B,C,D,E 表示这 5 种宝石。

每张发展卡上都标记了购买这张发展卡所需的 5 种宝石的数量 ai,0,bi,0,ci,0,di,0,ei,0

购买发展卡也有助于我们购买后面的发展卡。每张发展卡上还标记了我们以后每次买发展卡时可以抵扣每种里多少个宝石,记为 ai,1,bi,1,ci,1,di,1,ei,1。更形式化地说,小青鱼在购买发展卡 i 时,如果他已经购买的发展卡为集合 S,那么对于 A 类宝石,小青鱼只需要消耗 max(0,ai,0jSaj,1) 个。对于其余 4 种宝石同理。

发展卡也不是随意购买的。游戏初始时会将牌堆的前两张发展卡放到桌上(n=1 时,将牌堆中唯一一张发展卡放到桌上),每当小青鱼买走一张放在桌上的发展卡时,他就会从牌堆顶拿出下一张发展卡放到桌上。这样一来,除非牌堆已经被拿空,桌上始终都会有两张发展卡。

初始小青鱼没有任何宝石,也就买不了任何发展卡。游戏会进行很多轮,每一轮中,小青鱼可以进行两种操作之一:

  1. 选择两种不同的宝石,拿取这两种宝石各一个。

  2. 买走一张桌上的发展卡。

小青鱼想要知道,他最少进行几轮操作可以把 n 张发展卡全部买下。

这就到了考验你的宝石之力的时候了!你需要帮助小青鱼找到游戏的最优解,大胜 102B 宿舍的同学们。

输入格式

第一行一个正整数 n

接下来 n 行,每行 10 个整数 ai,0,bi,0,ci,0,di,0,ei,0,ai,1,bi,1,ci,1,di,1,ei,1,其中前 5 个数表示购买该发展卡所需的每种宝石数量,后 5 个数表示拥有该发展卡后能够提供的每种宝石数量。发展卡按照从牌堆顶到牌堆底的顺序给出。

输出格式

输出一个数,表示至少进行多少轮才能结束游戏。

样例一

input

5
1 1 1 1 1 0 0 0 0 1
0 0 0 0 5 1 0 0 0 0
2 1 0 0 0 0 0 0 0 1
0 0 2 2 0 0 1 1 0 0
2 1 1 0 0 0 0 0 0 1

output

12

explanation

一种可行的游戏过程如下:

第一轮:拿 A,E 两种宝石各一个。

第二轮:拿 B,E 两种宝石各一个。

第三轮:拿 C,E 两种宝石各一个。

第四轮:拿 D,E 两种宝石各一个。

第五轮:拿 D,E 两种宝石各一个。

第六轮:消耗 5E 类宝石买下第二张发展卡。

第七轮:消耗 1A 类宝石和 1B 类宝石买下第三张发展卡。

第八轮:拿 A,C 两种宝石各一个。

第九轮:消耗 2C 类宝石和 2D 类宝石买下第四张发展卡。

第十轮:消耗 1A 类宝石买下第五张发展卡。

第十一轮:拿 A,D 两种宝石各一个。

第十二轮:消耗 1D 类宝石买下第一张发展卡。

样例二

见附件下载。

数据范围

对于全部数据:

保证 1n50,ai,0,bi,0,ci,0,di,0,ei,0,ai,1,bi,1,ci,1,di,1,ei,10

M=max(ai,0,bi,0,ci,0,di,0,ei,0,ai,1,bi,1,ci,1,di,1,ei,1)。保证 M2000

子任务编号 n M 特殊性质 分值
1 20 2000 20
2 50 保证 bi,1=ci,1=di,1=ei,1=0 5
3 保证 ci,0=di,0=ei,0=0 5
4 保证 ci,1=di,1=ei,1=0 10
5 50 20
6 300 20
7 2000 20

时间限制:2s

空间限制:1GB