Beyond the Void
BYVoid
USACO 5.4.1 Canada Tour 周游加拿大 tour

这道题使我费了好大的劲才想出来,没有注意道题中只能自西向东的约定。如果没有这个约定,那就是个哈密尔顿圈问题了,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

相关日志