蒟蒻的想法

我是一只蒟蒻,说的不对欢迎大佬指正。
似乎没有人提出,治病的时候不会用两次同一种药。
证明:
1.连着用两次同种药是赤裸裸的浪费。
2.先用一次药,治好了某些病,过了一段时间又用了一次药。那么第一次的治疗是无效的,一段时间后再用药不会比原来差。

#include<bits/stdc++.h>
using namespace std;
int ans=1e9;
int n,m,a[110][110],q[(1<<12)+10];
bool v[110];
void search(int s,int f)//标准剪枝dfs,题解有类似方法
{
if(s==0){
if(f<ans) ans=f;
return;
}
if(f>=ans) return;
if(q[s]<=f) return;
else q[s]=f; 
int p=s;
for(int t=0;t<m;t++) if(v[t]){//v[t]记录是否用过这种药,用过则不用第二次
v[t]=false;
for(int i=0;i<n;i++){
if(a[t][i]==-1) s|=(1<<i);
if(a[t][i]==1 && s&(1<<i))
s^=(1<<i); 
}
if(s==0){
v[t]=true;
if(f+1<ans) ans=f+1;
return;
}
search(s,f+1);
v[t]=true;
s=p;
}
return;
}
int main()
{
scanf("%d",&n);
scanf("%d",&m);
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
scanf("%d",&a[i][j]);
}
}
memset(v,true,sizeof(v));
memset(q,127,sizeof(q));
search((1<<(n))-1,0);
if(ans>0&&ans<1e6)
printf("%d\n",ans);
else printf("The patient will be dead.\n");
return 0;
}

1 条评论

  • @ 2020-03-23 13:37:44

    spfa,注意毒解完了之后还可以中同样的毒…

    #include<cstdio>
    #include<queue>
    #define INF (1<<30)-1
    using namespace std;
    
    int n,m,s;
    queue<int> q;
    int a[105],b[105],d[(1<<10)+5];
    bool vis[(1<<10)+5];
    
    int readln()
    {
        int x=0,f=1;
        char ch=getchar();
        while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
        while ('0'<=ch&&ch<='9') x=x*10+ch-48,ch=getchar();
        return x*f;
    }
    
    inline int update(int x,int k)
    {
        x&=(~a[k]);x|=b[k];
        return x;
    }
    
    int main()
    {
        n=readln();m=readln();s=(1<<n)-1;
        for (int i=1;i<=m;i++)
            for (int j=0;j<n;j++)
            {
                int x=readln();
                if (x==1) a[i]|=(1<<j); else if(x==-1) b[i]|=(1<<j);
            }
        for (int i=0;i<=(1<<n)-1;i++) d[i]=INF;
        d[s]=0;q.push(s);vis[s]=true;
        while (!q.empty())
        {
            int x=q.front();
            vis[x]=false;q.pop();
            for (int i=1;i<=m;i++)
            {
                int y=update(x,i);
                if (d[y]>d[x]+1)
                {
                    d[y]=d[x]+1;
                    if (!vis[y]) {q.push(y);vis[y]=true;}
                }
            }
        }
        if (d[0]==INF) printf("The patient will be dead."); else printf("%d",d[0]);
        return 0;
    }
    
  • 1

信息

ID
1026
难度
5
分类
搜索 | 搜索与剪枝 点击显示
标签
(无)
递交数
3174
已通过
986
通过率
31%
被复制
2
上传者