Home » 国际竞赛 » Details

USACO 2015 US Open, Gold Problem 2. Palindromic Paths

Category: 国际竞赛, 计算机国际竞赛 Date: 2017年12月8日下午3:46

原题下载

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, r_{1}, r_{2})$ be the number of palindromic strings that we can build of length $2 a + 1$ , where the start of the string is on row $r_{1}$ , the end of the string is on row $r_{2}$ , 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, r_{1}, r_{2})$ 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})$ ^ $O (N^{3})$ algorithm which can be implemented in $O (N^{2})$ memory because you only need to keep track of $f (a, r_{1}, r_{2})$ and $f (a + 1, r_{1}, r_{2})$ concurrently over all possible pairs $(r_{1}, r_{2})$ .

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