Preparing NOJ

软件补丁问题

1000ms 65536K

Description:

      T公司发现其研制的一个软件中有n个错误,随即为该软件发放了一批共m个补丁程序。每一个补丁程序都有其特定的适用环境,某个补丁只有在软件中包含某些错误而同时又不包含另一些错误时才可以使用。一个补丁在排除某些错误的同时,往往会加入另一些错误。

换句话说,对于每一个补丁i,都有2 个与之相应的错误集合B1[i]B2[i],使得仅当软件包含B1[i]中的所有错误,而不包含B2[i]中的任何错误时,才可以使用补丁i。补丁i 将修复软件中的某些错误F1[i],而同时加入另一些错误F2[i]。另外,每个补丁都耗费一定的时间。

试设计一个算法,利用T 公司提供的m个补丁程序将原软件修复成一个没有错误的软件,并使修复后的软件耗时最少。

对于给定的n个错误和m个补丁程序,找到总耗时最少的软件修复方案。

Input:

       输入第1 行有2 个正整数n mn 表示错误总数,m表示补丁总数,1<=n<=20, 1<=m<=100

    接下来m行给出了m个补丁的信息。每行包括一个正整数,表示运行补丁程序i 所需时间,以及2 个长度为n的字符串,中间用一个空格符隔开。

    第1 个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于B1[i],若为“-”,则表示第k个错误属于B2[i],若为“0”,则第k个错误既不属于B1[i]也不属于B2[i],即软件中是否包含第k个错误并不影响补丁i的可用性。

    第2 个字符串中,如果第k个字符bk为“+”,则表示第k个错误属于F2[i],若为“-”,则表示第k个错误属于F1[i],若为“0”,则第k个错误既不属于F1[i]也不属于F2[i],即软件中是否包含第k个错误不会因使用补丁i 而改变。

Output:

  程序运行结束时,将总耗时数输出。如果问题无解,则输出0

Sample Input:

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

Sample Output:

8

Note:

 

本题由旧版NOJ导入,来源:算法设计与实验题解

Info

NOJ

Provider NOJ

Code NOJ1359

Tags

Submitted 0

Passed 0

AC Rate 0%

Date 04/20/2019 10:03:10

Related

Nothing Yet