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

观察发现，如果第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