本文正體字版由OpenCC轉換

這道題使我費了好大的勁纔想出來，沒有注意道題中只能自西向東的約定。如果沒有這個約定，那就是個哈密爾頓圈問題了，NP難。

題中所說的只能定向旅行，實際上取消了該題的後效性，可以用動態規劃來做。把返回的路線反向，假定有兩個人分別從起點到終點進行旅行，那麼整條路線就變成了兩條不相交的從起點到終點的路線。

狀態設定 f[i,j] 爲假定的甲乙兩人，甲走到第i個城市，乙走到第j個城市時，兩人走過的城市數目的和。

初始狀態 f[1,1]=1

狀態轉移方程 f[j,i]=f[i,j]=max{f[i,k]+1}(k到j存在飛機航線，1<=k<j) 交換甲乙，則肯定有f[j,i]=f[i,j]。

目標結果 由於題中告知必須走到終點才能返回，輸出結果一定是max{f[i,N]}(i到N存在飛機航線)。 如果沒有經過城市數目大於1的可行目標狀態，則無法完成這次環遊，輸出1。

這是加拿大IOI93的一道原題。在WC2008中聽吳教授說道，當時參加IOI的選手沒有人瞭解動態規劃，對這道題束手無策。選手們都用上了最複雜的搜索技巧，有人還寫了雙向搜索，可是都沒有通過。回國後開始研究，最終提出了動態規劃這一算法設計方法，於是動態規劃變成了之後競賽出題的熱點。

Compiling...
Compile: OK

Executing...
   Test 1: TEST OK [0.011 secs, 2892 KB]
   Test 2: TEST OK [0.011 secs, 2892 KB]
   Test 3: TEST OK [0.000 secs, 2888 KB]
   Test 4: TEST OK [0.000 secs, 2888 KB]
   Test 5: TEST OK [0.000 secs, 2888 KB]
   Test 6: TEST OK [0.000 secs, 2888 KB]
   Test 7: TEST OK [0.000 secs, 2888 KB]
   Test 8: TEST OK [0.022 secs, 2892 KB]
   Test 9: TEST OK [0.022 secs, 2892 KB]
   Test 10: TEST OK [0.000 secs, 2888 KB]
   Test 11: TEST OK [0.022 secs, 2892 KB]

All tests OK.

Your program ('tour') produced all correct answers! This is your submission #2 for this problem. Congratulations! 

/*
ID: cmykrgb1
PROG: tour
LANG: C++
*/

#include <iostream>
#include <fstream>
#include <string>
#define MAXN 101
#define INF 0x7FFFFFFF

using namespace std;

ifstream fi("tour.in");
ofstream fo("tour.out");

bool adj[MAXN][MAXN];
int f[MAXN][MAXN];
string City[MAXN];
int N,ans;

inline int getnum(string &s)
{
	for (int i=1;i<=N;i++)
		if (s==City[i])
			return i;
}

void init()
{
	int i,V,d1,d2;
	string C1,C2;
	fi >> N >> V;
	for (i=1;i<=N;i++)
		fi >> City[i];
	for (i=1;i<=V;i++)
	{
		fi >> C1 >> C2;
		adj[d2][d1]=adj[d1=getnum(C1)][d2=getnum(C2)]=true;
	}
}

void dynamic()
{
	int i,j,k;
	f[1][1]=1;
	for (i=1;i<=N;i++)
	{
		for (j=i+1;j<=N;j++)
		{
			f[i][j]=-INF;
			for (k=1;k<j;k++)
			{
				if (adj[k][j] && f[i][k]>0 && f[i][k]>f[i][j])
					f[i][j]=f[i][k];
			}
			f[j][i]=++f[i][j];
			j=j;
		}
	}
}

void print()
{
	int i;
	ans=1;
	for (i=1;i<N;i++)
		if (adj[i][N] && f[i][N]>ans)
			ans=f[i][N];
	fo << ans << endl;
	fi.close();
	fo.close();
}

int main()
{
	init();
	dynamic();
	print();
	return 0;
}

上次修改時間 2017-02-03