正文

codevs2594解药还是毒药(状压dp)

安  安  2022-09-05  440

关键词：

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

1 0 1

-1 1 0

样例输出 Sample Output

数据范围及提示 Data Size & Hint

1≤n≤10

0<m≤100

#include<iostream>
#include<cstdio>
#include<cstring>

#define inf 1e8
#define N 2500

using namespace std;
int n,m,g[1007][1007],f[N];

int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=m;i++) for(int j=1;j<=n;j++)
      scanf("%d",&g[i][j]);
    for(int i=0;i<=(1<<n);i++) f[i]=inf;f[0]=0;
    for(int i=0;i<(1<<n);i++)
      for(int j=1;j<=m;j++)
      {
            int S=i;//i为当前状态 
            for(int k=1;k<=n;k++)//转移 
            {
                if(g[j][k]==0) continue;
                if(g[j][k]==1) S=S|(1<<k-1);//0变1,1不变 
                if(g[j][k]==-1 && S&(1<<k-1)) S^=(1<<k-1);//1变0 
          }
          f[S]=min(f[S],f[i]+1);//S为i能转移到的状态 
      }
    if(f[(1<<n)-1]==inf)printf("The patient will be dead.
");
    else printf("%d
",f[(1<<n)-1]);
    return 0;
}

解药还是毒药codevs2594状态压缩bfs

我们用二进制来压缩状态，每一位上的0/1对应该位的病症是否存在对于药剂的治愈与致病效果分开储存如果状态a，要使用i药剂，i药剂的治愈效果是b，致病效果是c，那么状态a就可以转移为：（a-（a&b））|c用宽搜可以保证时... 查看详情

2594解药还是毒药

...nbsp; 题目描述 DescriptionSmart研制出对付各种症状的解药，可是他一个不小心，每种药都小小地配错了一点原料，所以这些药都有可能在治愈某些病症的同时又使人患上某些别的病症（你可能会问那…那是解药还是毒药... 查看详情

codevs1358棋盘游戏(状压dp)

1358棋盘游戏时间限制:1s 空间限制:64000KB 题目等级:大师Master 题目描述 Description这个游戏在一个有10*10个格子的棋盘上进行，初始时棋子位于左上角，终点为右下角，棋盘上每个格子内有一个0到9的数... 查看详情

codevs2800送外卖（状压dp）

题目描述 Description有一个送外卖的，他手上有n份订单，他要把n份东西，分别送达n个不同的客户的手上。n个不同的客户分别在1~n个编号的城市中。送外卖的从0号城市出发，然后n个城市都要走一次（一个城市可以走多次），... 查看详情

tyvj3308毒药解药题解

题目大意这些药都有可能在治愈某些病症的同一时候又使人患上某些别的病症……经过我天才的努力。最终弄清了每种药的详细性能，我会把每种药能治的病症和能使人患上的病症列一张清单给你们，然后你们要依据这张清单找... 查看详情

codevs2596售货员的难题(状压dp)

2596售货员的难题时间限制:1s 空间限制:32000KB 题目等级:钻石Diamond 题目描述 Description某乡有n个村庄(1<n<＝15)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)是已知的，且... 查看详情

[codevs1050]棋盘染色2（状态压缩dp）

...以为这题是插头DP，结果今天一看发现不用>_<，虽然还是状压DP。因为只有5列，所以查看详情

当人工智能遇上“全球头号网红”元宇宙是毒药还是解药？

“几款好游戏、几部好电影对于元宇宙打造的推力并不大”2021年年度热词，“元宇宙”必须拥有姓名。随着电影《头号玩家》的走红和Facebook的改名，“元宇宙”这个曾经沉睡在上世纪九十年代科幻小说里的旧词活跃了... 查看详情

状压dp初探·总结

...;状态压缩其实是一种并没有改变dp本质的优化方法，阶段还是要照分，状态还是老样子，决策依旧要做，转移方程还是得列，最优还是最优，无后还是无后，所以它比较好理解。状压，顾名思义就是要将一些状压想办法压缩... 查看详情

动态规划---状压dp2(代码片段)

今天模拟，状压dp又没写出来。。。还是不会啊，所以今天搞一下这个状压dp。这里有一道状压dp的板子题：CornFields就是一道很简单的状压裸题，但是要每次用一个二进制数表示一行的状态。附加一个关于位运算的总结：上题干... 查看详情

hdu1074-doinghomework-[状压dp]

可以说是第一道状压DP题，至少感觉这道题目还是挺简单的，不算很难理解；题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1074TimeLimit:2000/1000MS(Java/Others)MemoryLimit:65536/32768K(Java/Others)ProblemDescriptionIgnatiushasjustcome 查看详情

状压dp学习笔记（紫例题集）(代码片段)

...觉不太能用滚动数组，所以那这个题学习一下状压dp思想还是勉强可以的1/*2（可以不看）3（窃窃地）废话：4想了半天还是写一篇题解吧，尽管有点麻烦。。。。5但这题的确做了不下十几节课。。。。。6不写一篇对不起这几天... 查看详情

dp状压dp

...的小鸟，当时菜得连题目都没看懂，不过现在回过头来看还是挺简单的，那么我们再来看看这道题吧。题意&数据范围看这考虑预处理出两个点构成的抛物线，因为经过原点，所以对于二次函数ax2+bx+c因此已知两个点(x1,y1),(x2,w2... 查看详情

20个问题（状压dp）

...特征。每个物体用一个m位01串表示，表示每个特征是具备还是不具备。我在心里想一个物体，由你来猜。你每次可以询问一个特征，然后我会告诉你：我心里的物体是否具备这个特征。当你确定答案之后，就把答案告诉我。如果... 查看详情

[scoi2005]互不侵犯(状压$dp$)(代码片段)

题目链接Solution状压(dp).(f[i][j][k])代表前(i)列中,已经安置(j)位国王,且最后一位状态为(k).然后就可以很轻松的转移了...记忆化搜索还是不够啊...只能会正向(dp).Code#include<bits/stdc++.h>#definelllonglongusingnamespacestd;llf[10][101][1100], 查看详情

poj3254--cornfields--状压dp

...leInput23111010SampleOutput9题解：　　状压dp的基础题啊qwq但我还是写了有一会儿……（完全忘了这种题的套路了）　　这道题加入了一点搜索的思想，因为你有两个限制（本来就不能种+旁边已经种了所以不能种），用它们去进行剪... 查看详情

hdu1074doinghomeworkdp状压dp

...压DP，我们可以用一个15位二进制数来表示各个课程做完还是没做完，然后从S从1到1<<N枚举i从1到N枚举，如果S&(1 查看详情

poj2288(状压dp)

...发现是因为存在一个特殊情况，即n==1时需要特判，哎，还是自己想的不周到1#include<string>2#include<cstring>3#include<cstdio>4#include<ios 查看详情