HBC24220宝藏男孩,动态规划[USACO 2015 Ope G]Palindromic Paths题解

不断提升技能，才能在职场中立于不败之地！全网最全C++题库，助您成为编程领域的佼佼者。

Farmer John's farm is in the shape of anN×NN×Ngrid of fields , each labeled with a letter in the alphabet. For example: ABCD. Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome , since she gets confused about which direction she had walked. Please help Bessie determine the number of distinct routes she can take that correspond to palindromes. Different ways of obtaining the same palindrome count multiple times. Please print your answer modulo 1,000,000,007.

Farmer John's farm is in the shape of an N×NN×N grid of fields (1≤N≤5001≤N≤500), each labeled with a letter in the alphabet. For example: ABCD BXZX CDXB WCBA Each day, Bessie the cow walks from the upper-left field to the lower-right field, each step taking her either one field to the right or one field downward. Bessie keeps track of the string that she generates during this process, built from the letters she walks across. She gets very disoriented, however, if this string is a palindrome (reading the same forward as backward), since she gets confused about which direction she had walked. Please help Bessie determine the number of distinct routes she can take that correspond to palindromes. Different ways of obtaining the same palindrome count multiple times. Please print your answer modulo 1,000,000,007.

标签： HBC24220宝藏男孩 动态规划[USACO 2015 Ope G]Palindromic Paths题解