USACO 2015 US Open, Gold Problem 2. Palindromic Paths

原題下載

USACO2015OPEN-G2

答案

(Analysis by Nick Wu)

This is a DP problem where we iteratively count the number of palindromes that we can build from the middle.

Let?f(a,r1,r2)?be the number of palindromic strings that we can build of length?2a+1, where the start of the string is on row?r1, the end of the string is on row?r2, and the middle of the string is on the diagonal of the grid that goes from the top-right to the bottom-left of the grid. We initialize?f(0,i,i)=1?for all possible rows. Because of the constraints of the DP state, the beginning and ending squares are uniquely determined by their row. Therefore,?f(a,r1,r2)?affects at most four other quantities:f(a+1,r1,r2), f(a+1,r1?1,r2),f(a+1,r1,r2+1), and f(a+1,r1?1,r2+1).

This gives an?O(N^3)?algorithm which can be implemented in?O(N^2)?memory because you only need to keep track of?f(a,r1,r2)?and?f(a+1,r1,r2)?concurrently over all possible pairs?(r1,r2).

Here is my code.

import java.io.*;
import java.util.*;
public class palpathG {
  static int n;
  public static void main(String[] args) throws IOException {
    BufferedReader br = new BufferedReader(new FileReader("palpath.in"));
    PrintWriter pw = new PrintWriter(new BufferedWriter(new FileWriter("palpath.out")));
    n = Integer.parseInt(br.readLine());
    char[][] grid = new char[n][n];
    for(int i = 0; i < n; i++) {
      String s = br.readLine();
      for(int j = 0; j < n; j++) {
        grid[i][j] = s.charAt(j);
      }
    }
    long[][] dp = new long[n][n];
    for(int i = 0; i < n; i++) {
      dp[i][i] = 1;
    }
    final long MOD = 1000000007;
    for(int num = n-1; num >= 1; num--) {
      long[][] next = new long[n][n];
      for(int a = 0; a < n; a++) {
        int rowA = a;
        int colA = (num-1-a);
        if(colA < 0) continue;
        for(int b = 0; b < n; b++) {
          int rowB = b;
          int colB = 2*n-num-rowB-1;
          if(colB >= n) continue;
          if(grid[rowA][colA] != grid[rowB][colB]) continue;
          next[rowA][rowB] += dp[rowA][rowB];
          if(rowA+1 < n) next[rowA][rowB] += dp[rowA+1][rowB];
          if(rowB-1 >= 0) next[rowA][rowB] += dp[rowA][rowB-1];
          if(rowA+1 < n && rowB-1 >= 0) next[rowA][rowB] += dp[rowA+1][rowB-1];
          next[rowA][rowB] %= MOD;
        }
      }
      dp = next;
    }
    pw.println(dp[0][n-1]);
    pw.close();
  }
}

以上就是關于【USACO 2015 US Open, Gold Problem 2. Palindromic Paths】的解答，如需了解學校/賽事/課程動態，可至翰林教育官網獲取更多信息。

往期文章閱讀推薦：

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

2026理工科競賽“大洗牌”：線上考試終結、報名門檻收緊、晉級規則重塑...你準備好了嗎？