2594 解药如故毒药

2594 解药还是毒药,2594解药毒药

时间限制: 1 s  空间限制: 128000
KB  题目等级 : 钻石
Diamond 题解  查看运行结果    
题目描述 Description

Smart研制出对付各种症状的解药,可是他一个不小心,每种药都小小地配错了一点原料,所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症(你可能会问那…那是解药还是毒药啊?)……,经过Smart的努力,终于弄清了每种药的具体性能,他会把每种药能治愈的病症和能使人患上的病症列一张清单给你,然后你要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声,病症的数目不超过10种,而且他的药是用不完的,就是说每种药剂都可以被重复使用。

输入描述 Input Description

给你们的单子里第一行是病症的总数n(1≤n≤10)。第二行是药剂的种类m(0<m≤100)。

以下有m行,每行有n个数字用空格隔开,文件的第i+2行的n个数字中,如果第j个数为1,就表示第i种药可以治愈病症j(如果患有这种病的话则治愈,没有这种病则无影响),如果为0表示无影响,如果为-1表示反而能使人得上这种病(无病患上,有病无影响)。Smart制的药任何两种性能都不同。

输出描述 Output Description

你只要输出用的最少的药剂数就可以了,其实还有可能用尽了所有的药也不能将所有病治愈,那样的话你们只要输出“The patient will be dead.”就可以了。

样例输入 Sample Input

3

2

1 0 1

-1 1 0

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

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 }

 

解药还是毒药,2594解药毒药 时间限制: 1 s
空间限制: 128000 KB 题目等级 : 钻石 Diamond 题解 查看运行结果 题目描述
Description Smart研制出对…

分类标签 Tags 点此展开 

 

动态规划 启发式搜索 搜索

#include<iostream>
#include<queue>
using namespace std;
int f[101][11],a[1025],n,m;
queue<int>que;
int js[12];
int main()
{//状压js[]+宽搜que 
    js[1]++;
    for(int i=2;i<=11;i++)
        js[i]=js[i-1]<<1;
    cin>>n>>m;
    for(int i=1;i<=m;i++)
        for(int j=1;j<=n;j++)
            cin>>f[i][j];
    int k=js[n+1]-1;
    que.push(k);
    while(!que.empty()){
        int p=que.front();
        que.pop();
        if(!p){
            cout<<a[p]<<endl;
            return 0;
        }
        for(int i=1;i<=m;i++){
            int s=0;
            for(int j=1;j<=n;j++){
                if(f[i][j]==0&&(p&js[j])){
                    s+=js[j];
                }
                if(f[i][j]==-1){
                    s+=js[j];
                }
            }
            if(!a[s]&&s!=k){
                a[s]=a[p]+1;
                que.push(s);
            }
        }
    }
    cout<<"The patient will be dead."<<endl;
    return 0;
}

 

1 0 1

2594 解药还是毒药

 

 时间限制: 1
s

 空间限制: 128000
KB

 题目等级 : 钻石
Diamond

题解

 

 

 

题目描述 Description

Smart研制出对付各种症状的解药,可是他一个不小心,每种药都小小地配错了一点原料,所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症(你可能会问那…那是解药还是毒药啊?)……,经过Smart的努力,终于弄清了每种药的具体性能,他会把每种药能治愈的病症和能使人患上的病症列一张清单给你,然后你要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声,病症的数目不超过10种,而且他的药是用不完的,就是说每种药剂都可以被重复使用。

输入描述 Input Description

给你们的单子里第一行是病症的总数n(1≤n≤10)。第二行是药剂的种类m(0<m≤100)。

以下有m行,每行有n个数字用空格隔开,文件的第i+2行的n个数字中,如果第j个数为1,就表示第i种药可以治愈病症j(如果患有这种病的话则治愈,没有这种病则无影响),如果为0表示无影响,如果为-1表示反而能使人得上这种病(无病患上,有病无影响)。Smart制的药任何两种性能都不同。

输出描述 Output Description

你只要输出用的最少的药剂数就可以了,其实还有可能用尽了所有的药也不能将所有病治愈,那样的话你们只要输出“The patient will be dead.”就可以了。

样例输入 Sample Input

3

2

1 0 1

-1 1 0

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

1≤n≤10

0<m≤100

 

 

 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 }

 

Smart研制出对付各种症状的解药,可是他一个不小心,每种药都小小地配错了一点原料,所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症(你可能会问那…那是解药还是毒药啊?)……,经过Smart的努力,终于弄清了每种药的具体性能,他会把每种药能治愈的病症和能使人患上的病症列一张清单给你,然后你要根据这张清单找出能治愈所有病症的最少药剂组合……顺便说一声,病症的数目不超过10种,而且他的药是用不完的,就是说每种药剂都可以被重复使用。

输入描述 Input Description

-1 1 0

样例输入 Sample Input

题解

0<m≤100

发表评论

电子邮件地址不会被公开。 必填项已用*标注