icon

2018-11-24

USACO Canada Tour

一道可以用DP解的题,貌似在CLRS上有类似的。问题的关键在于如何保证来回的路线上没有重合的点,这里用状态转移来保证。

用$f(i, j)$表示从$i$点出发,向西走到最西边的点,然后往回走到$j$点,每个点至多走一次, 最多可以经过的点的个数。根据对称性$f(i, j) = f(j, i)$,只要考虑$i > j$的情况即可。

初始情况,

当$i>j$时,

根据$f(i,j)$的定义,我们不会走到大于$max(i,j)$的点,又因为$k,j<i$,所以$f(k,j)$一定不经过$i$点。

因此只要$f(k,j)$满足条件,$f(i,j)$就满足,根据归纳法就知道$f(i,j)$一定满足条件。

据说还可以用最大流解。

/*
ID: mwx36mw2
TASK: tour
LANG: C++11
*/
// Author: Wenxing Mei
//   Date: 2018-11-21 11:57
#include <bits/stdc++.h>
#ifdef LOCAL
#include <unistd.h>
#endif
using namespace std;
#define rep(i, a, b) for (int i = (int)a; i < (int)b; ++i)
#define per(i, b, a) for (int i = (int)b - 1; i >= (int)a; --i)
#define repv(ele, cont) for (auto &ele : cont)
#define all(x) x.begin(), x.end()
#define mp make_pair
#define eb emplace_back
#define ep emplace
#define fi first
#define se second
typedef long long ll;
typedef pair<int, int> ii;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ii> vii;
typedef vector<ll> vll;
// END OF TEMPLATE

int main() {
#ifndef LOCAL
  freopen("tour.in", "r", stdin);
  freopen("tour.out", "w", stdout);
  ios_base::sync_with_stdio(0), cin.tie(0);
#endif
  int n, v;
  cin >> n >> v;
  map<string, int> s2i;
  string s;
  rep(i, 0, n) {
    cin >> s;
    s2i[s] = n - 1 - i;
  }
  vvi g(n, vi(n, 0));
  rep(i, 0, n) g[i][i] = 1;

  string a, b;
  rep(i, 0, v) {
    cin >> a >> b;
    int x = s2i[a], y = s2i[b];
    g[x][y] = g[y][x] = 1;
  }

  vvi dp(n, vi(n, 0));
  dp[0][0] = 1;

  rep(i, 1, n) {
    rep(j, 0, i) {
      rep(k, 0, i) {
        if (k && (k == j)) continue;
        if (g[k][i] && dp[k][j]) {
          dp[i][j] = max(dp[i][j], dp[k][j] + 1);
        }
      }
      dp[j][i] = dp[i][j];
    }
  }

  int ans = 0;
  rep(i, 0, n - 1) {
    if (g[n - 1][i]) ans = max(ans, dp[n - 1][i]);
  }
  ans = max(ans, 1);
  cout << ans << '\n';

  return 0;
}
comments powered by Disqus

search See also