USACO 2016 January Contest, Gold Problem 2. Radio Contact

Category: 计算机国际竞赛 Date: 2017年11月9日上午10:53

原题下载

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】的解答，如需了解学校/赛事/课程动态，可至翰林教育官网获取更多信息。

往期文章阅读推荐：

美国AI奥赛首次新增低龄组！2027 USAAIO报名中，2月正式开考！

不考编程实操？2026 CAICP人工智能能力认证首轮11月22日开考，备考指南速递！