【USACO 5.4.1】Canada Tour-白红宇

【USACO 5.4.1】Canada Tour

阅读量：4684 次

发布时间：2019-06-09

本文共 1468 字，大约阅读时间需要 4 分钟。

题目大意

　　给出一个序列，序列中的每个元素是一个字符串。然后输入哪些元素可以互相到达。计算可以到达城市最多这样的一条路径，从序列开始的元素到达序列末端元素，再从序列末端元素返回序列开始元素，这条路径中所到达的元素不能重复（除起点外）。序列最长是100.

题解

　　明显我们可以发现这样的一件事：从起点到达终点和从终点到达起点并没有什么不同。

　　所以，现在我们考虑两条从起点到达终点并且不相交的两条路径即可。

　　我们现在考虑一条路径怎么做。显然是使用DP：f[目前到达元素i] = max{f[j | 从起点可以到达j并且j可到达i且j < i] + 1}, f[起点] = 1

　　类似的。我们求两条路径也是差不多。f[第一条路径到达元素i][第二条路径到达元素j] = max{f[k | 同上][j], f[i][k | 同上]} + 1

　　最后求答案的是再枚举那两个元素可以到达终点。算法复杂度是O(N³)

　　至此，问题被完美地解决了。

　　代码和上述表达有稍微差别。

/*TASK:tourLANG:C++*/#include 
     
      #include 
      
       #include 
       
        #include 
        #include 
         
          using namespace std;int f[105][105], ans, n, v;string s1, s2;map
          
            getid;bool g[105][105];int main(){ freopen("tour.in", "r", stdin); freopen("tour.out", "w", stdout); scanf("%d%d", &n, &v); for (int i = 0; i < n; ++i) { cin >> s1; getid[s1] = i; } memset(g, false, sizeof(g)); while (v--) { cin >> s1 >> s2; int x = getid[s1], y = getid[s2]; g[x][y] = g[y][x] = true; } memset(f, 0, sizeof(f)); f[0][0] = 1; for (int k = 0; k < n; ++k) for (int i = 0; i <= k; ++i) for (int j = 0; j <= k; ++j) if (f[i][j] > 0){ if (k != i && g[j][k]) f[i][k] = max(f[i][k], f[i][j] + 1); if (k != j && g[i][k]) f[k][j] = max(f[k][j], f[i][j] + 1); } ans = 1; for (int i = 0; i < n; ++i) if (g[i][n - 1]) for (int j = 0; j < n; ++j) if (i != j && g[j][n - 1]) ans = max(ans, f[i][j] + 1); printf("%d\n", ans); return 0;}

转载于:https://www.cnblogs.com/albert7xie/p/5224224.html

你可能感兴趣的文章