本文正體字版由OpenCC轉換

看到這道題的時候，我的第一感覺就是類似於石子歸併的動態規劃，因爲有合併和環的明顯特徵。但是經過分析，直接套用石子歸併的方法是很難解決的，於是重新考慮這道題。

觀察發現，如果第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