Wednesday, July 1, 2015

USACO US Open 2015 Contest Gold - Palindromic Paths

문제 링크(Problem Link)

  우선, 첫 번째로 관찰할 수 있는 게 주어진 그리드가 N by N이어서 생성되는 string들의 길이는 항상 (2N-1)이다. 따라서 길이는 항상 홀수이며 그 가운데에 위치하는 문자는 그리드에서 오른쪽 위에서 왼쪽 아래로 내려가는 대각선 위에 위치하게 된다.
  여기서 착안해서 다음과 같이 DP Table을 정의할 수 있다.
  D(L , a , b) = 가운데에서 양쪽으로 뻗어나가는 길이가 현재 L이고, 왼쪽으로 L번째 문자가 a번째 행까지, 오른쪽으로 L번째 문자가 b번째 행까지 고려됬을 때 가능한 가짓 수
  저기서 a랑 b들은 L에 따라서 위치할 수 있는 곳들이 각각의 대각선들로 정해지는데 탐색하는 순서는 큰 상관 없는 것 같다. 결론적으로 S[a][col(a)] == S[b][col(b)]라면
  D(L, a, b) = D(L-1, a, b) + D(L-1, a-1, b) + D(L-1, a, b+1) + D(L-1, a-1, b+1)이 된다. 만약 해당 좌표가 그리드의 크기를 넘어가면 0으로 처리하면 된다.  답은 D(n-1, 1, n)에 위치한다.

No comments:

Post a Comment