比赛场次 516
比赛名称 EYOI暨SBOI暑假快乐赛6th
比赛状态 已结束比赛成绩
开始时间 2022-06-30 08:30:00
结束时间 2022-06-30 12:00:00
开放分组 全部用户
注释介绍 EYOI暨SBOI2022暑假的第六场比赛!
暑假热身赛第六,题都不是很难哦!
细心审题,尽力拿到可以拿到的分数!
注意题目难度不是按照题目编号依次递增!
题目名称 软件补丁
输入输出 bugs.in/out
时间限制 1000 ms (1 s)
内存限制 128 MiB
测试点数 8 简单对比
用户 结果 时间 内存 得分
Gravatar该账号已注销 WWWWWWAW 0.000 s 0.00 MiB 12
GravatarHeSn WWWWWWAW 0.000 s 0.00 MiB 12
Gravatar┭┮﹏┭┮ WWWWWWAW 0.000 s 0.00 MiB 12
Gravatarop_组撒头屯 WWWWWWAW 0.000 s 0.00 MiB 12
Gravatarムラサメ WWWWWWAW 0.000 s 0.00 MiB 12
Gravatar康尚诚 WWWWWWAW 0.000 s 0.00 MiB 12
Gravatarcb WWWWWWAW 0.000 s 0.00 MiB 12
Gravatar➥Q小白小黑233 WWWWWWAW 0.000 s 0.00 MiB 12
Gravatar遥时_彼方 WWWWWWAW 0.000 s 0.00 MiB 12

软件补丁

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

【问题描述】

对于一个软件公司来说,在发行一个新软件之后,可以说已经完成了工作。但是实际上,许多软件公司在发行一个新产品之后,还经常发送补丁程序,修改原产品中的错误(当然,有些补丁是要收费的)。

如某微硬公司就是这样的一个软件公司。今年夏天,在发行了一个新的字处理软件之后,到现在他们已经编写了许多补丁程序。仅仅在这个周末,他们就用新编写的补丁程序解决了软件中的一个大问题。而在每一个补丁程序修改软件中的某些错误时,有可能引起软件中原来存在的某些错误重新发作。发生这种情况是因为当修改一个错误时,补丁程序利用了程序中约定的特别行为,从而导致错误的重新产生。

微硬公司在他们的软件中一共发现了 $n$ 个错误$B$={$b_l$,$b_2$,…,$b_n$},现在他们一共发送了 $m$ 个补丁程序$p_1,p_2,…,p_m$。如果想要在软件中应用第 $p_i$ 号补丁程序,则软件中必须存在错误$B+i ≤B$,并且错误$B-i≤B$必须不存在(显然,$B+i∩B-i$为空集)。然后,这个补丁程序将改正错误 $F-i≤B$(如果错误存在的话),并且产生新错误$F+i≤B$(同样,$F+i∩F-i$也为空集)。

现在,微硬公司的问题只有一个。他们给出一个原始版本的软件,软件包含了$B$中的所有错误,然后按照某一顺序在软件中应用补丁程序(应用某个补丁程序时,软件必须符合该补丁程序的应用条件,且运行该程序需要一定的时间)。问怎样才能最快地改正软件中的所有错误(即为修正所有错误而运行的补丁程序的总时间最短)?

【输入格式】

文件的第一行包含两个整数$n$和$m$,分别表示软件中的错误个数和发送的补丁个数。其中,$n$和$m$满足条件:$1≤n≤20,1≤m≤100$。

接下来的 $m$ 行(即第$2$行至第$m+1$行)按顺序描述了$m$个补丁程序的情况,第$i$行描述第$i-1$号补丁程序。每一行包含一个整数(表示在软件中应用该补丁程序所需的时间,单位为秒)和两个$n$个字符的字符串(中间均用一个空格分开)。

第一个字符串描述了应用该补丁程序(第$i-1$号)的条件,即说明在软件中某错误应该存在还是不应该存在。字符串的第$i$个字符,如果是“$+$”,表示在软件中必须存在$b_i$号错误;如果是“$-$”,表示软件中错误$b_i$不能存在;如果是“$0$",则表示错误$b_i$存在或不存在均可(即对应用该补丁程序没有影响)。

第二个字符串描述了应用该补丁程序(第$i-1$号)后的效果,即应用补丁程序后,哪些错误被修改好了,而又产生了哪些新错误。字符串的第$i$个字符,如果是“$+$”,表示产生了一个新错误$b_i$;如果是“$-$”,表示错误$b_i$被修改好了;如果是“$0$”,则表示错误$b_i$不变(即原来存在,则仍然存在;原来不存在,则也不存在)。

【输出格式】

请你找到一个应用补丁程序的最优顺序,修改软件中的所有错误,并且所用的时间最少。

注意,每个补丁程序是可以应用多次的。

如果存在这样一个序列,请在输出文件的第一行输出应用补丁程序的总时间(单位为秒);如果找不到这样一个序列,请在输出文件的第一行输出$-1$。

【输入样例】

3 3
1 000 00-
1 00- 0-+
2 0-- -++

【输出样例】

8

【样例解释】

软件初始时共有编号为$1,2,3$三个$bug$,使用第一种补丁,满足其使用条件 使用后还有编号为$1,2$的两个$bug$,继续使用第二种补丁,当前状态有$2$号$bug$,没有$3$号$bug$,满足使用条件,使用后有$1,3$两个$bug$ 然后依次使用1,3,1,2,1补丁,得到时间最小值为8