- 毒药?解药?
- 2018-02-26 19:55:05 @
我是一只蒟蒻,说的不对欢迎大佬指正。
似乎没有人提出,治病的时候不会用两次同一种药。
证明:
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 条评论
-
孙鹤鸣 (sunheming) LV 10 @ 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