Problem1069--[视频]动态规划入门(二维一边推2:顺序对齐)

1069: [视频]动态规划入门(二维一边推2:顺序对齐)

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 3  Solved: 3
[Status] [Submit] [Creator:]

Description

【问题描述】

考虑两个字符串右对齐的最佳解法。例如,有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。

AAD_DEFGGHC          

 ADCDE__GH_           

每一个数值匹配的位置值2分,一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数,在上述给定的例子中,6个位置(A,D,D,E,G,H)匹配,三段空格,所以得分2*6+(-1)*3=9,注意,我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符,则既不得分也不失分。

请你写个程序找出最佳右对齐方案。

 

【输入文件】

输入文件包含两行,每行一个字符串,最长50个字符。字符全部是大字字母。

 

【输出文件】

一行,为最佳对齐的得分。





状态的定义需要根据题意的特殊性

Sample Input Copy

AADDEFGGHC
ADCDEGH

Sample Output Copy

9

Source/Category