USACO 2014 December Contest, Silver Problem 2. Marathon

Category: 计算机国际竞赛 Date: 2017年12月5日上午11:17

原题下载

USACO2014-DEC-S2

答案

(Analysis by Nick Wu)

Let's define $f (n, k)$ to be the smallest distance needed to end up at point $n$ having skipped exactly $k$ points.

Given that we are at a specific point, if we knew that we wanted to skip $x$ points, then we would want to know $f (n - x - 1, k - x)$ . However, we don't know what the optimal number is. We can try all possible numbers of points to skip - this gives us an $O (n k^{2})$ algorithm.

Here is my Java solution, which computes all $f (n, k)$ values in a bottom-up fashion.

import java.io.*;
import java.util.*;
public class marathonS {
  
  static int[] x, y;
  
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("marathon.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("marathon.out")));
    StringTokenizer st = new StringTokenizer(br.readLine());
    int n = Integer.parseInt(st.nextToken());
    int k = Integer.parseInt(st.nextToken());
    x = new int[n];
    y = new int[n];
    for(int i = 0; i < n; i++) {
      st = new StringTokenizer(br.readLine());
      x[i] = Integer.parseInt(st.nextToken());
      y[i] = Integer.parseInt(st.nextToken());
    }
    int[][] dp = new int[k+1][n];
    for(int i = 0; i < dp.length; i++) {
      Arrays.fill(dp[i], 1 << 30);
    }
    dp[0][0] = 0;
    for(int i = 0; i <= k; i++) {
      for(int j = 0; j < n; j++) {
        for(int l = j+1; l < n && i + l-j-1 <= k; l++) {
          int nextI = i + (l-j-1);
          int nextJ = l;
          dp[nextI][nextJ] = Math.min(dp[nextI][nextJ], dp[i][j] + distBetween(j, l));
        }
      }
    }
    pw.println(dp[k][n-1]);
    pw.close();
  }
  
  public static int distBetween(int i, int j) {
    return dist(x[i], y[i], x[j], y[j]);  
  }

  public static int dist(int x1, int y1, int x2, int y2) {
    int x = x1-x2;
    int y = y1-y2;
    return Math.abs(x) + Math.abs(y);
  }

}

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

往期文章阅读推荐：

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

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