USACO 2016 January Contest, Gold Problem 2. Radio Contact

原題下載

USACO2016-JAN-G2

答案:

(Analysis by Mark Gordon)

This problem is actually a veiled?Dynamic Time Warping?problem where the error function is the squared distance between FJ and Bessie.

Therefore the problem can be solved with dynamic programming. For each possible position of Farmer John and Bessie we can compute the minimum energy required for them to both get to their end position by trying to step FJ forward, step Bessie forward, our move them both forward.

Here's my code implementing this solution.

#include <iostream>
#include <vector>
#include <cstring>
#include <cstdio>
#include <map>

using namespace std;

#define INF 0x7FFFFFFFFFFFFFFFLL

long long memo[1010][1010];

vector<pair<long long, long long> > F;
vector<pair<long long, long long> > B;

long long solve(int fi, int bi) {
  /* The energy cost of the radio for this timestep. */
  long long base = (F[fi].first - B[bi].first) * (F[fi].first - B[bi].first) +
             (F[fi].second - B[bi].second) * (F[fi].second - B[bi].second);
  if (fi + 1 == F.size() && bi + 1 == B.size()) {
    return base;
  }

  long long& ref = memo[fi][bi];
  if (ref != -1) return ref;

  /* Don't include the cost of the first timestep. */
  if (fi == 0 && bi == 0) base = 0;

  ref = INF;
  if (fi + 1 < F.size()) {
    /* Step FJ forward. */
    ref = min(ref, base + solve(fi + 1, bi));
  }
  if (bi + 1 < B.size()) {
    /* Step Bessie forward. */
    ref = min(ref, base + solve(fi, bi + 1));
  }
  if (fi + 1 < F.size() && bi + 1 < B.size()) {
    /* Step both forward. */
    ref = min(ref, base + solve(fi + 1, bi + 1));
  }
  return ref;
}

int main() {
  freopen("radio.in", "r", stdin);
  freopen("radio.out", "w", stdout);

  map<char, int> dx, dy;
  dx['E'] = 1; dx['W'] = -1;
  dy['N'] = 1; dy['S'] = -1;

  int N, M;
  cin >> N >> M;
  int fx, fy, bx, by;
  cin >> fx >> fy >> bx >> by;
  string SF, SB;
  cin >> SF >> SB;

  /* Compute FJ's path. */
  F.push_back(make_pair(fx, fy));
  for (int i = 0; i < SF.size(); i++) {
    fx += dx[SF[i]];
    fy += dy[SF[i]];
    F.push_back(make_pair(fx, fy));
  }

  /* Compute Bessie's path. */
  B.push_back(make_pair(bx, by));
  for (int i = 0; i < SB.size(); i++) {
    bx += dx[SB[i]];
    by += dy[SB[i]];
    B.push_back(make_pair(bx, by));
  }

  memset(memo, -1, sizeof(memo));
  cout << solve(0, 0) << endl;
  return 0;
}

以上就是關(guān)于【USACO 2016 January Contest, Gold Problem 2. Radio Contact】的解答，如需了解學(xué)校/賽事/課程動(dòng)態(tài)，可至翰林教育官網(wǎng)獲取更多信息。

往期文章閱讀推薦：

NOAI人工智能奧賽 2026-2027 活動(dòng)章程出爐：新規(guī)則必看！

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動(dòng)：留學(xué)申請(qǐng)的“核武器”來了！