原题来自:APIO 2007
新建的圆形动物园是亚太地区的骄傲。圆形动物园坐落于太平洋的一个小岛上,包含一大圈围栏,每个围栏里有一种动物。如下图所示:
你是动物园的公关主管。你要做的是,让每个参观动物园的游客都尽可能高兴。今天有一群小朋友来到动物园参观,你希望能让他们在动物园度过一段美好的时光。但这并不是一件容易的事——有些小朋友喜欢某些动物,而有些小朋友则害怕某些动物。例如, Alex 喜欢可爱的猴子和考拉,而害怕拥有锋利牙齿的狮子。而 Polly 会因狮子有美丽的鬃毛而喜欢它,但害怕有臭味的考拉。
你可以选择将一些动物从围栏中移走以使得小朋友不会害怕。但你移走的动物也不能太多,否则留给小朋友们观赏的动物就所剩无几了。
每个小朋友站在大围栏圈的外面,可以看到连续的 5 个围栏。你得到了所有小朋友喜欢和害怕的动物信息。当下面两处情况之一发生时,小朋友就会高兴:
1、至少有一个他害怕的动物被移走;
2、至少有一个他喜欢的动物没被移走。
例如,考虑下图中的小朋友和动物:
假如你将围栏 4 和 12 的动物移走。Alex 和 Ka-Shu 将很高兴,因为至少有一个他们害怕的动物被移走了。这也会使 Chaitanya 高兴,因为他喜欢的围栏 6 和 8 中的动物都保留了。但是,Polly 和 Hwan 将不高兴,因为他们看不到任何他们喜欢的动物,而他们害怕的动物都还在。这种安排方式使得三个小朋友高兴。
现在换一种方法,如果你将围栏 4 和 6 中的动物移走,Alex 和 Polly 将很高兴,因为他们害怕的动物被移走了。Chaitanya 也会高兴,虽然他喜欢的动物 6 被移走了,他仍可以看到围栏 8 里面他喜欢的动物。同样的 Hwan 也会因可以看到自己喜欢的动物 12 而高兴。唯一不高兴的只有 Ka-Shu。
如果你只移走围栏 13 中的动物,Ka-Shu 将高兴,因为有一个他害怕的动物被移走了,Alex, Polly, Chaitanya 和 Hwan 也会高兴,因为他们都可以看到至少一个他们喜欢的动物。所以有 5 个小朋友会高兴。这种方法使得了最多的小朋友高兴。
14 5 2 1 2 4 2 6 3 1 1 6 4 6 1 2 9 6 8 8 1 1 9 12 12 3 0 12 13 2
5