文章目錄

• • 題目描述
  • 題解：
  • 代碼：

添加鏈接描述

題目描述

T 公司發現其研制的一個軟件中有 n 個錯誤，隨即為該軟件發放了一批共 m
個補丁程序。每一個補丁程序都有其特定的適用環境，某個補丁只有在軟件中包含某些錯誤而同時又不包含另一些錯誤時才可以使用。一個補丁在排除某些錯誤的同時，往往會加入另一些錯誤。

換句話說，對于每一個補丁 i，都有 2 個與之相應的錯誤集合 B1[i]和 B2[i]，使得僅當軟件包含 B1[i]中的所有錯誤，而不包含
B2[i]中的任何錯誤時，才可以使用補丁 i。補丁 i 將修復軟件中的某些錯誤 F1[i]，而同時加入另一些錯誤
F2[i]。另外，每個補丁都耗費一定的時間。

試設計一個算法，利用 T 公司提供的 m 個補丁程序將原軟件修復成一個沒有錯誤的軟件，并使修復后的軟件耗時最少。對于給定的 n 個錯誤和 m
個補丁程序，找到總耗時最少的軟件修復方案。

輸入格式

第 1 行有 2 個正整數 n 和 m，n 表示錯誤總數，m表示補丁總數，1<=n<=20, 1<=m<=100。

接下來 m 行給出了 m 個補丁的信息。每行包括一個正整數，表示運行補丁程序 i 所需時間，以及 2 個長度為 n
的字符串，中間用一個空格符隔開。

第 1 個字符串中，如果第 k 個字符 bk 為“+”，則表示第 k 個錯誤屬于 B1[i]，若為“-”，則表示第 k 個錯誤屬于
B21[i]，若為“0”，則第 k 個錯誤既不屬于 B1[i]也不屬于 B2[i]，即軟件中是否包含第 k 個錯誤并不影響補丁 i
的可用性。

第 2 個字符串中，如果第 k 個字符 bk為“-”，則表示第 k 個錯誤屬于 F1[i]，若為“+”，則表示第 k 個錯誤屬于
F2[i]，若為“0”，則第 k 個錯誤既不屬于 F1[i]也不屬于 F2[i]，即軟件中是否包含第 k 個錯誤不會因使用補丁i 而改變。

輸出格式

程序運行結束時，將總耗時數輸出。如果問題無解，則輸出 0。

輸入輸出樣例
輸入

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

輸出

8

題解：

樣例分析：
圓圈表示還沒修復，三角表示已修復
按照題目所給要求以及樣例讀入，我們可以得到以下分析
所采用的補丁分別為補丁1,2，1,3，1,2，1.
然后錯誤全部修復，總耗時為8

思路：
我是在刷網絡流24題遇到的，看完后怎么想也想不到網絡流。。。
感覺dp或者是最短路？
看了題解還真是，妙啊 ~ ~ （啥玩意還帶這么坑人的）
還真是網絡流24題中沒網絡流，老婆餅里沒老婆
借用一張照片

第一步： 怎么和最短路聯系到一起？
最短路無疑就是起點，終點，中間點，還有各點之間的線段
前三種點都是節點，在本題中節點就是錯誤修復的狀態，起點就是全沒修復，終點就是全修復了，每次修復一些錯誤或者新添一些錯誤，此時的修復狀態就是當前狀態。線段長度就是運行補丁的時間。我們在輸入每一個補丁的時候，可以枚舉一種狀態，如果當前狀態可以使用補丁，就算出使用補丁后的狀態，前狀態連一條邊到后狀態，長度也就是補丁時長
第二步： 狀態壓縮
n<=20，也就是最多20個錯誤，而每個錯誤只有修好和沒修好倆狀態，我們可以用01來表示（1表示沒修好，0表示修好），這樣20個錯誤其實就是一個01串，
比如bug3已經修好，1和2還未修好，那01串就是110，轉化成十進制就是6。而初始狀態（都未修好）為111，對應7。結束狀態是都修好了為000，對應0。當有n個錯誤時，初始狀態就是n個1，十進制也就是2ⁿ-1，即（1<<n）-1。結束就是0
第三步： 狀態轉移
補丁使用是有嚴格要求的，有些位置為1，有些位置為0，才能使用
題目中有b1，b2，f1，f2
軟件包含b1錯誤，不包含b2錯誤，能夠修復f1，加入錯誤f2
我們看看補丁3

0-- -++

使用狀態：（判斷一個補丁包能否使用）
b1是000=0（因為第一個字符串里面沒有+）
b2是011=3（第一個字符串中 第二三位是-）
記當前狀態為x
1.判斷x中b1位上是否都為1（說明x是否含有b1錯誤）
我們可以將x與b1按位與。如果得到的值是b1本身，那就說明x的b1位上都是1
2.判斷x中b2位上是否都為0（說明x是否含有b2錯誤）
也是將b2與x按位與，如果得到的都是0，說明x的b2位上都是0

if((x&p[i].b1)==p[i].b1 && (x&p[i].b2)==0)//說明該補丁包可以使用

修復狀態：（使用后的情況）
使用后，f1位置會修好變成0，f2會變成1。
當前狀態為x，如果要將f2位置變成1，直接x或上f2即可。f1位置變成0，我們可以或上一個f1，使得當前狀態的所有f1位置都變成1，再異或一個f1，這樣就可以將f1所有位置變成0.

int y=((x|p[i].f1)|p[i].f2)^p[i].f1;

應該算講的很詳細了吧!

代碼：

//第一個字符串中+ //第二個字符串- #include<bits/stdc++.h> #define Maxn 100 #define Maxm 100 #define Maxnum 4000000using namespace std;inline int read(){char c=getchar();int x=0,f=1;while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}return x*f; }int n,m; int ST;struct debug{int b1;int b2;int f1;int f2;int T; }hero[Maxm+2];priority_queue < pair<int,int> > q; int dist[Maxnum]; int vis[Maxnum]; void dj(){memset(dist,0x3f,sizeof(dist));dist[ST]=0;q.push(make_pair(0,ST));while(!q.empty()){int now=q.top().second;q.pop();if(vis[now]==1) continue;vis[now]=1;for(int i=1;i<=m;i++){if( (hero[i].b1&now)==hero[i].b1 && (hero[i].b2&now)==0 ){int v=((now|hero[i].f1)^hero[i].f1)|hero[i].f2;if(dist[now]+hero[i].T<dist[v]){dist[v]=dist[now]+hero[i].T;q.push(make_pair(-dist[v],v));}}}} }int main(){n=read(); m=read();for(int i=1;i<=n;i++)ST=ST|(1<<i);//ST表 cout<<ST<<endl;for(int i=1;i<=m;i++){hero[i].T=read();string B,F;cin>>B>>F;for(int j=0;j<=n-1;j++){if(B[j]=='+')hero[i].b1=hero[i].b1|(1<<(j+1));if(B[j]=='-')hero[i].b2=hero[i].b2|(1<<(j+1));if(F[j]=='+')hero[i].f2=hero[i].f2|(1<<(j+1));if(F[j]=='-')hero[i].f1=hero[i].f1|(1<<(j+1));}}dj();if(dist[0]==dist[Maxnum-1])cout<<"0";elsecout<<dist[0];return 0; } 創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的P2761 软件补丁问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。