ZJU/ZOJ 1792 Gap Punishment Aligment Problem 解题报告

题目大意是给出两个字符串进行匹配，如果两个字符串的长度不等则用空格将其补齐，如果两个字符串匹配的对应位置字符相等则得2分，不等（不包括空格匹配）扣两分。如果用空格进行匹配则连续的k个空格（在同一个字符串中）的得分为-(4+k)。问两个字符串匹配的最高得分是多少。

依然是LCS（最长公共子串）的模型，由于要考虑空格匹配得分的影响，可以将每次匹配分为三种情况考虑：

1. 原有字符之间的匹配
2. 上一次匹配在第一个字符串里补空格
3. 上一次匹配在第二个字符串里补空格

由此可以得到的状态转移方程：

• f[i,j,0]:=max(f[i-1,j-1,0],max(f[i-1,j-1,1],f[i-1,j-1,2]))+2(s1[i]=s2[j]) or f[i,j,0]:=max(f[i-1,j-1,0],max(f[i-1,j-1,1],f[i-1,j-1,2]))-1(s1[i]<>s2[j]);
• f[i,j,1]:=max(max(f[i,j-1,0],f[i,j-1,2])-5,f[i,j-1,1]-1);
• f[i,j,2]:=max(max(f[i-1,j,0],f[i-1,j,1])-5,f[i-1,j,2]-1);

s1[i]表示的是第一个字符串的第i个字符，s2[j]表示的是第二个字符串的第j个字符。f[i,j,0]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用s1[i]与s2[j]进行匹配的最高得分，f[i,j,1]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用空格与s2[j]进行匹配的最高得分，f[i,j,2]表示的是用s1的前i个字符与s2的前j个字符匹配，且当前用s1[i]与空格进行匹配的最高得分。初始化f[i,0]=-(4+i),f[0,i]=-(4+i);

1652376    2008-09-30 21:05:35     Accepted    1792    FPC    10    3340    IwfWcf