USACO 5.4 Canada Tour

Canada Tour

You have won a contest sponsored by an airline. The prize is a ticket to travel around Canada, beginning in the most western point served by this airline, then traveling only from west to east until you reach the most eastern point served, and then coming back only from east to west until you reach the starting city. No city may be visited more than once, except for the starting city, which must be visited exactly twice (at the beginning and the end of the trip). You are not allowed to use any other airline or any other means of transportation.

Given a list of cities served by the airline and a list of direct flights between pairs of cities, find an itinerary which visits as many cities as possible and satisfies the above conditions beginning with the first city and visiting the last city on the list and returning to the first city.

PROGRAM NAME: tour

INPUT FORMAT

Line 1:	The number N of cities served by the airline and the number V of direct flights that will be listed. N will be a positive integer not larger than 100. V is any positive integer.
Lines 2..N+1:	Each line contains a name of a city served by the airline. The names are ordered from west to east in the input file. There are no two cities in the same meridian. The name of each city is a string of, at most, 15 digits and/or characters of the Latin alphabet; there are no spaces in the name of a city.
Lines N+2..N+2+V-1:	Each line contains two names of cities (taken from the supplied list), separated by a single blank space. This pair is connected by a direct, two-way airline flight.

SAMPLE INPUT (file tour.in)

8 9	
Vancouver		
Yellowknife	
Edmonton
Calgary
Winnipeg
Toronto	
Montreal
Halifax	
Vancouver Edmonton
Vancouver Calgary	
Calgary Winnipeg
Winnipeg Toronto
Toronto Halifax
Montreal Halifax
Edmonton Montreal
Edmonton Yellowknife
Edmonton Calgary

OUTPUT FORMAT

Line 1:

The number M of different cities visited in the optimal itinerary. Output 1 if no itinerary is possible.

SAMPLE OUTPUT (file tour.out)

Namely: Vancouver, Edmonton, Montreal, Halifax, Toronto, Winnipeg, Calgary, and Vancouver (but that's not a different city).

——————————————————————————————————题解

NOCOW里说，中国选手在这场比赛的时候，不知道动态规划是什么（IOI93）然后这一年之后，动态规划在各大竞赛多了起来

dp[i,j]表示两个人从1走到i和从1走到j经过的城市总数，dp[i,j]=dp[j,i] dp[1,1]=1

dp[i,j]=dp[j,i]=max{dp[i][k]+1} 1=<k<j 同时k->j有路径同时dp[i][k]>0

那么答案是max{dp[k][N]} 要求k->N有路径

这样不会重复，因为如果要重复一定经过某个重复的点，dp[k][k]是不合法的，不会被处理，从而它之后的状态也不会被处理，而所有重复状态一定是两个人都经过这个重复点之后的状态，故而不会重复

这样的更新，相当于固定一个人不动，让另一个人走，走的人不被允许走经过固定这个人的路即可

字符串的处理用map

 1 /*
 2 ID: ivorysi
 3 LANG: C++
 4 PROG: tour
 5 */
 6 #include <iostream>
 7 #include <cstdio>
 8 #include <cstring>
 9 #include <algorithm>
10 #include <queue>
11 #include <set>
12 #include <vector>
13 #include <string.h>
14 #include <cmath>
15 #include <stack>
16 #include <map>
17 #define siji(i,x,y) for(int i=(x);i<=(y);++i)
18 #define gongzi(j,x,y) for(int j=(x);j>=(y);--j)
19 #define xiaosiji(i,x,y) for(int i=(x);i<(y);++i)
20 #define sigongzi(j,x,y) for(int j=(x);j>(y);--j)
21 #define inf 0x3f3f3f3f
22 #define ivorysi
23 #define mo 97797977
24 #define hash 974711
25 #define base 47
26 #define pss pair<string,string>
27 #define MAXN 5000
28 #define fi first
29 #define se second
30 #define pii pair<int,int>
31 #define esp 1e-8
32 typedef long long ll;
33 using namespace std;
34 int n,m;
35 map<string,int> rec;
36 string cit,str1,str2;
37 int f[105][105],used[105],dp[105][105],ans;
38 void solve() {
39     scanf("%d%d",&n,&m);
40     siji(i,1,n) {
41         cin>>cit;
42         rec[cit]=i;
43     }
44     siji(i,1,m) {
45         cin>>str1>>str2;
46         f[rec[str1]][rec[str2]]=1;
47         f[rec[str2]][rec[str1]]=1;
48     }
49     dp[1][1]=1;
50     siji(i,1,n) {
51         siji(j,i+1,n) {
52             xiaosiji(k,1,j) {
53                 if(dp[i][k]>0 && f[k][j]==1) dp[i][j]=max(dp[i][k]+1,dp[i][j]);
54             }
55             dp[j][i]=dp[i][j];
56         }
57     }
58     ans=1;
59     siji(i,1,n) {
60         if(f[i][n]==1) ans=max(ans,dp[i][n]);
61     }
62     printf("%d
",ans);
63 }
64 int main(int argc, char const *argv[])
65 {
66 #ifdef ivorysi
67     freopen("tour.in","r",stdin);
68     freopen("tour.out","w",stdout);
69 #else
70     freopen("f1.in","r",stdin);
71 #endif
72     solve();
73     return 0;
74 }