和众位神牛的方法不同，我使用了IDS+位运算+hash

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 447ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 322ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
————————-
Accepted 有效得分：100 有效耗时：769ms

也许Vijos的数据出的是无心的，但遇到了“有心”偷懒的我，用了一个比较WS的IDS，结果第四个点TLE了。
N次改变代码退出顺序，又寄希望于Puppy，结果依然TLE。
后来套来了输出数据，加了一个不大合理的“剪枝”：until ansDeep>=5
终于第四个不超时了，但第10个点剪过了，输出答案错误。
又改成until ansDeep>=5 ，结果第10个过了，第4个又超时了。。。

无奈，考验RP的时候到了
until ansDeep>=5+random(2);
交了两次，在Puppy的帮助下，终于AC了。。。。。。

声明：谁要是拿我的代码去刷这个题结果导致AC率的下降，与本人无关！
（谁叫你cheat来着。。。。。）

源代码如下：

program vijos_1026;

const
maxM=100;
maxH=1023;

var
n,m:longint;
bTrue,bFalse:array[1..maxM] of longint;
h:array[0..maxH] of boolean;

procedure init;
var
i,j,t:longint;
begin
readln(n);
readln(m);
for i:=1 to m do begin
for j:=1 to n do begin
read(t);
case t of
1:bTrue[i]:=bTrue[i] or (1<<(j-1));
-1:bFalse[i]:=bFalse[i] or (1<<(j-1));
end;
end;
readln;
end;
end;

procedure IDS;
var
ansDeep:longint;
noAns:boolean;

procedure print(d:longint);
begin
if d>-1 then writeln(d)
else writeln(‘The patient will be dead.’);
halt;
end;

procedure _IDS(deep:longint;now:longint);
var
i:longint;
begin
if h[now] then exit;
h[now]:=true;
if deep=ansDeep then begin
noAns:=false;
if now=(1<<n)-1 then print(ansDeep);
h[now]:=false;
exit;
end;
for i:=1 to m do
_IDS(deep+1,(now or bTrue[i]) and (not bFalse[i]));
h[now]:=false;
end;

begin
ansDeep:=0;
randomize;
fillChar(h,sizeof(h),0);
repeat
noAns:=true;
inc(ansDeep);
_IDS(0,0);
until noAns or (ansDeep>=5+random(2));
print(-1);
end;

begin
init;
IDS;
end.

Malash
2009年10月10日 下午

这个题与Vijos 1019 补丁VS错误极为相似。对于1019这个题，许多人都想到了将每种状态对应成图中的点，每次安装补丁对应一条边，然后求一下单源最短路——SPFA。该算法写起来简单，效率也很高。

那么对于1026这道题，是不是也能这样做呢？

如果你有这个想法，然后去百度一下，结果只能是被泼了一盆凉水——第一条搜索结果赫然写着：“显然是一个NP问题……只能考虑搜索。”

据我猜测，许多人因此放弃了这个想法。

但我不认为此题必须要用搜索。在今天下午我用极其WS的方法Cheat掉这个题后，我又考虑了一下这个问题，发现转图的想法并没有不合理的地方。晚上（刚才），我用了不到15分钟写出了代码，并一次AC

编译通过…
├ 测试数据 01：答案正确… 0ms
├ 测试数据 02：答案正确… 0ms
├ 测试数据 03：答案正确… 0ms
├ 测试数据 04：答案正确… 0ms
├ 测试数据 05：答案正确… 0ms
├ 测试数据 06：答案正确… 0ms
├ 测试数据 07：答案正确… 0ms
├ 测试数据 08：答案正确… 0ms
├ 测试数据 09：答案正确… 0ms
├ 测试数据 10：答案正确… 0ms
————————-
Accepted 有效得分：100 有效耗时：0ms

秒杀。。。。

原理其实很简单，由于病症最多只有10个，可以转化成二进制，最大为1024-1。我们将所有可能出现的病症组合情况转为十进制后作为图的顶点，对于每一个点i，枚举每一种药品k，用位运算得出该组合转变为的组合j，然后在i和j间连一条权值为1的边。最后用Dijkstra或其他算法计算出全病0到痊愈1 shl n-1之间的最短路径长度，即为答案。若不存在路径则无解。

源代码如下：
program vijos_1026;

const
maxN=10;
maxM=100;
maxV=1<<maxN-1;
maxLong=maxLongint>>2;

var
n,m,v:longint;
bTrue,bFalse:array[1..maxM] of longint;
a:array[0..maxV,0..maxV] of longint;

procedure init;
var
i,j,t:longint;
begin
readln(n);
v:=1<<n-1;
readln(m);
for i:=1 to m do begin
for j:=1 to n do begin
read(t);
case t of
1:bTrue[i]:=bTrue[i] or (1<<(j-1));
-1:bFalse[i]:=bFalse[i] or (1<<(j-1));
end;
end;
readln;
end;
end;

procedure main;
var
i,j,k:longint;
begin
fillDWord(a,sizeof(a)>>2,maxLong);
for i:=0 to v do begin
a[i,i]:=0;
for k:=1 to m do begin
j:=(i or bTrue[k]) and (not bfalse[k]);
if a[i,j]>1 then a[i,j]:=1;
end;
end;
end;

function dijkstra(s,t:longint):longint;
var
i,j,k,min:longint;
d:array[0..maxV] of longint;
b:array[0..maxV] of boolean;
begin
for i:=0 to v do d[i]:=a[s,i];
fillChar(b,sizeof(b),false);
b[s]:=true;
for i:=1 to v do begin
min:=maxLong;
for j:=0 to v do
if (not b[j]) and (d[j]<min) then begin
min:=d[j]; k:=j;
end;
if min=maxLongint then exit(d[t]);
if k=t then exit(d[t]);
b[k]:=true;
for j:=0 to v do
if (not b[j]) and (d[j]>d[k]+a[k,j]) then
d[j]:=d[k]+a[k,j];
end;
exit(d[t]);
end;

procedure print;
var
ans:longint;
begin
ans:=Dijkstra(0,1<<n-1);
if ans<maxLong then writeln(ans)
else writeln(‘The patient will be dead.’);
end;

begin
init;
main;
print;
end.

最后，我想引用写作《背包问题九讲》的dd_engi大牛的一句话：
“思考”是一个OIer最重要的品质。简单的问题，深入思考以后，也能发现更多。”

Malash

2009年10月11日0:03:00