2594 解藥還是毒藥

Smart研製出對付各種癥狀的解藥，可是他一個不小心，每種藥都小小地配錯了一點原料，所以這些藥都有可能在治愈某些病癥的同時又使人患上某些別的病癥（你可能會問那…那是解藥還是毒藥啊？）……，經過Smart的努力，終於弄清了每種藥的具體性能，他會把每種藥能治愈的病癥和能使人患上的病癥列一張清單給你，然後你要根據這張清單找出能治愈所有病癥的最少藥劑組合……順便說一聲，病癥的數目不超過10種，而且他的藥是用不完的，就是說每種藥劑都可以被重覆使用。

給你們的單子里第一行是病癥的總數n（1≤n≤10）。第二行是藥劑的種類m（0<m≤100）。

以下有m行，每行有n個數字用空格隔開，文件的第i+2行的n個數字中，如果第j個數為1，就表示第i種藥可以治愈病癥j（如果患有這種病的話則治愈，沒有這種病則無影響），如果為0表示無影響，如果為-1表示反而能使人得上這種病（無病患上，有病無影響）。Smart制的藥任何兩種性能都不同。

你只要輸出用的最少的藥劑數就可以了，其實還有可能用盡了所有的藥也不能將所有病治愈，那樣的話你們只要輸出“The patient will be dead.”就可以了。

3

2

1 0 1

-1 1 0

2

1≤n≤10

0<m≤100

用dp[i]表示到達第i種狀態所需要的最小步數

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<cmath>
 5 #include<queue>
 6 #include<algorithm>
 7 #define lli long long int 
 8 using namespace std;
 9 const int MAXN=1001;
10 const int maxn=0x7fffff;
11 inline void read(int &n)
12 {
13     char c='+';int x=0;bool flag=0;
14     while(c<'0'||c>'9')
15     {c=getchar();if(c=='-')flag=1;}
16     while(c>='0'&&c<='9')
17     {x=(x<<1)+(x<<3)+c-48;c=getchar();}
18     flag==1?n=-x:n=x;
19 }
20 int a[MAXN][MAXN];
21 int dp[MAXN];
22 int n,m;
23 int main()
24 {
25     read(n);read(m);
26     for(int i=1;i<=m;i++)
27         for(int j=1;j<=n;j++)
28             read(a[i][j]);
29     for(int i=0;i<=(1<<n);i++)
30         dp[i]=maxn;
31     dp[0]=0;
32     for(int i=0;i<=(1<<n);i++)
33     {
34         for(int j=1;j<=m;j++)
35         {
36             int now=i;
37             for(int k=1;k<=n;k++)
38             {
39                 if(a[j][k]==0)    continue;
40                 if(a[j][k]==1)    now=now|(1<<k-1);
41                 if(a[j][k]==-1&&now&(1<<k-1))    now^=(1<<k-1);    
42             }
43             dp[now]=min(dp[now],dp[i]+1);
44         }
45     }
46     if(dp[(1<<n)-1]==maxn)printf("The patient will be dead.\n");
47     else printf("%d\n",dp[(1<<n)-1]);
48     return 0;
49 }