Beyond the Void
BYVoid
POI 1999 步兵问题 Musketeers

看到这道题的时候,我的第一感觉就是类似于石子归并的动态规划,因为有合并和环的明显特征。但是经过分析,直接套用石子归并的方法是很难解决的,于是重新考虑这道题。

观察发现,如果第i个人想与第j个人决斗(i<j),i,j必须相邻,也就是i,j之间的人必须全部被打败。还句话说,如果i,j相邻,一定存在一个k(i<k<j),使得i,k相邻,k与j相邻,而且i可以打败k或者j可以打败k。这样就把问题缩小了,可以以此进行动态规划。考虑到是一个环,我们可以把N个人复制一遍,接在后面。

设定状态 F[i,j] 表示第i个人是否可以与第j个人相邻 (1<=i<j<=N*2),第i个人在环上另一面的映射为i+N

状态转移方程 F[i,j]= Or { F[i,k]=F[k,j]=true | i可以打败k或j可以打败k }

边界条件 由于i和i+1两个一定是相邻的,所以有 F[i,i+1]=true

判断第i个人可以胜出,只要存在k,使得i可以战胜k,并且F[i,k]=F[k,i+N]=true。F[i,k]和F[k,i+N]分别为i到k在环上的两个方向,两个方向上的人都必须被打败,才能判断i胜出。

/* 
 * Problem: POI1998 mus
 * Author: Guo Jiabao
 * Time: 2008.12.10 20:48:07
 * State: Solved 
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>

using namespace std;

const int MAXN=201;

bool F[MAXN][MAXN];
bool Beat[MAXN][MAXN];
int N,N2,Wcnt;
bool win[MAXN];

void init()
{
	int i,j;
	char c;
	freopen("mus.in","r",stdin);
	freopen("mus.out","w",stdout);
	scanf("%d",&N);
	N2=N*2;
	for (i=1;i<=N;i++)
	{
		for (j=1;j<=N;j++)
		{
			c=getchar();
			while (c==10 || c==13) c=getchar();
			Beat[i][j]=Beat[i][j+N]=Beat[i+N][j]=Beat[i+N][j+N]= c=='1';
		}
	}
}

void dynamic()
{
	int i,j,k,l;
	for (i=1;i<N2;i++)
	{
		F[i][i+1]=true;
	}
	for (l=3;l<=N;l++)
	{
		for (i=1;i<=N2;i++)
		{
			if ((j=i+l-1)>N2)
				break;
			for (k=i+1;k<=j-1;k++)
			{
				if (F[i][k] && F[k][j] && (Beat[i][k] || Beat[j][k]))
				{
					F[i][j]=true;
					break;
				}
			}
		}
	}
	for (i=1;i<=N;i++)
	{
		for (k=i+1;k<i+N;k++)
		{
			if (F[i][k] && F[k][i+N] && Beat[i][k])
			{
				win[i]=true;
				Wcnt++;
				break;
			}
		}
	}
	printf("%dn",Wcnt);
	for (i=1;i<=N;i++)
	{
		if (win[i])
		{
			printf("%dn",i);
		}
	}
}

int main()
{
	init();
	dynamic();
	return 0;
}
<h2><span class="mw-headline">步兵问题 </span></h2>

在Louis三世和他的重臣-红衣主教Richelieu时期的一个旅馆里n个步兵正在大口的吃肉喝酒。由于喝个不停,因此步兵们热心于吵架。一场喝醉了酒的争吵爆发了,每个步兵都谩骂着对方。

决斗是不可避免的。但是谁应该以什么顺序去打谁?他们决定(第一个回合来自他们的共同争吵)他们围成一圈按顺序选出一些人。被选出的士兵和他右边相邻的人打斗。失败的人离开游戏,为了更加精确,他的尸体将被仆人拖走。下一个步兵将站在失败者的旁边成为胜利者的邻居。

一些年后,当历史学家读了胜利者的记录后,他们意识到最终胜利的结果依靠一个按决斗顺序展开的圆环。他们注意到一个栅栏练习表明,谁靠着谁 能赢得一场决斗。它表现在(用数学语言)“A赢B”的关系不是及物的!步兵A比B打的更好,B比C更好,C比A更好是有可能的。当然,他们三个当中的首场 决斗影响了最后的结果。如果A和B先打,那么C最终会赢。但是如果B和C先打,那么A就最终会赢。历史学家被他们的发现感到入迷,决定去核实那么步兵能够 生存。法国的命运和整个文明的欧洲真正依靠这个!

任务

N个人以从1到n的连贯数字站成一行。他们要决斗n-1次。在第一个回合这些人中的一个(编号为I)打他右边的邻居,也就是编号为 I+1(如果I=n,则要打的人为编号为1的)。一个失败者离开游戏,圆环收缩以至下一个人能成为胜利者的邻居。我们被给出可能的决斗结果的表,用一个矩 阵形式。如果Ai,j = 1,那么编号为I的人总是战胜编号为j的人。如果Ai,j = 0,那么编号为I的人输给编号为j的人。如果存在一系列n-1的图,我们说编号为k的人赢得了这个游戏,赢得了最终的决斗。

写一个程序:

从文件读取矩阵A,  计算可能赢得比赛的人的编号,  把结果写到文件

输入

在文件的首行有一个整数n(满足不等式3&lt;=n&lt;=100)被记录。在接下来的n行的每一行里将出现有0或1组成的n位的字符 串。一个第I行第j列的数字表示Ai,j 。当然,对于i&lt;&gt;j ,Ai,j = 1 - Aj,i 。对于每一个I,Ai,i = 1。

输出

在输入文件的首行,应该写下m-可能赢得这个游戏的人数。在接下来的m行里,这些人的编号应该被按照升序记录,每一行一个。

样例输入
<pre>7
1111101
0101100
0111111
0001101
0000101
1101111
0100001</pre>
样例输出
<pre>3
1
3
6</pre>
备注

决斗顺序:1-2,1-3, 5-6, 7-1, 4-6, 6-1 得到最后胜利的是编号为6的人。你也能检查仅有两个人(1和3)更有可能赢得这个游戏。

上次修改时间 2017-02-03

相关日志