
ZOJ Problem Set  1792
Consider two strings X = x1x2 ... xm and Y = y1y2 ... yn over an alphabet set sigma = {A, G,C, T}. Denote sigma* = sigma + {}, where "" (dash) is the symbol that represents a space (or blank) in strings. A string alignment is to align X and Y and form two strings X*, Y* over the alphabet sigma* such that: 1. the two strings X*, Y* have the same lengths, and 2. ignoring dashes, the string X* is the same as the string X, and the string Y* is the same as the string Y. As an example, an alignment of two strings 'GATCCGA' and 'GAAAGCAGA' is as follows: GATCCGA There are three gaps in the above alignment; here a gap is defined as a string of consecutive dashes. Now, let us consider the following alignment: GATCCGA Here are two gaps within this alignment. The rule of measuring the intermittent gap punishment alignment score (abbreviated by GPS) is as follows: If xi is aligned with yj, the score is o If a (consecutive) subsequence of xi's (or yj's) is aligned with a gap of length k, the score is defined as (4 + k). That is, in the first alignment example given above, its GPS is 2  (4 + 1) + 2  (4 + 2)  (4 + 1) + 2  1 + 2 + 2 = 7. For the second alignment, its GPS is 2 + 2  (4 + 3)  (4 + 1) + 2  1 + 2 + 2 = 3. Given two strings, the problem we would like to solve is to find an alignment such that its GPS is maximized. Thus, in our example, the best alignment is GATCCGA Its GPS is 2+2(4+2)1+21+2+2=2. In our problem, m and n are at most 500. Furthermore, it is required that no space in one sequence is aligned with a space in another.
The input format is as follows: 1. The first line contains an integer n of sequence pairs; the number n is
at most 50.
For each pair of sequences, output the maximum GPS in one line.
3
18 Source: Asia 2003, Kaohsiung (Taiwan China) 