USACO 2014 December Contest, Silver Problem 2. Marathon

原題下載

USACO2014-DEC-S2

答案

(Analysis by Nick Wu)

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

Given that we are at a specific point, if we knew that we wanted to skip xx points, then we would want to know f(n?x?1,k?x)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(nk2)O(nk2) algorithm.

Here is my Java solution, which computes all f(n,k)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】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

NOAI、UKOAI、USAAIO三大AI奧賽新賽季全面啟動：留學申請的“核武器”來了！

耗時一年備考 USACO 卻毫無收獲？一文教你找準最佳備考起步時間！