這道題使我費了好大的勁纔想出來，沒有注意道題中只能自西向東的約定。如果沒有這個約定，那就是個哈密爾頓圈問題了，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;
}