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;
}

以上就是关于【USACO 2016 January Contest, Gold Problem 2. Radio Contact】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

USACO计算机奥赛如何认证成绩？2026赛季黄金铂金组“定时开赛”规则详解！

USACO计算机奥赛考试语言是什么？C++、Python、Java选哪个效率最高？