今天在刷DP进行曲 结果第一题就被码了 悲催 求高手给思路
【问题描述】
考虑两个字符串右对齐的最佳解法。例如，有一个右对齐方案中字符串是AADDEFGGHC和ADCDEGH。
AAD_DEFGGHC
ADCDE__GH_
每一个数值匹配的位置值2分，一段连续的空格值-1分。所以总分是匹配点的2倍减去连续空格的段数，在上述给定的例子中，6个位置（A，D，D，E，G，H）匹配，三段空格，所以得分2*6+(-1)*3=9，注意，我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符，则既不得分也不失分。
请你写个程序找出最佳右对齐方案。
【输入文件】
输入文件包含两行，每行一个字符串，最长50个字符。字符全部是大字字母。
【输出文件】
一行，为最佳对齐的得分。
【输入输出样例】
输入：AADDEFGGHCADCDEGH
输出：
9

var
f:array[0..60,0..60]of longint;
st1,st2:string;
s1,s2:array[0..60]of char;
i,j,k,code,ans:longint;
procedure init;
begin
assign(input,'align.in');
assign(output,'align.out');
reset(input);
rewrite(output);
end;
procedure readdata;
begin
readln(st1);
readln(st2);
for i:=1 to length(st1) do
s1[length(st1)-i+1]:=st1[i];
for i:=1 to length(st2) do
s2[length(st2)-i+1]:=st2[i];
end;
procedure main;
begin
fillchar(f,sizeof(f),$ff);
f[0,0]:=0;
ans:=0;
for i:=1 to length(st1) do
for j:=1 to length(st2) do
begin
f[i,j]:=f[i-1,j-1];
if s1[i]=s2[j] then f[i,j]:=f[i,j]+2;//两个字符相等，就在原有的基础上+2
for k:=1 to i-1 do
if f[k,j]-1>f[i,j] then f[i,j]:=f[k,j]-1;
for k:=1 to j-1 do
if f[i,k]-1>f[i,j] then f[i,j]:=f[i,k]-1;//两个for循环都是处理空格的。目的就是考虑如果要错开一个空格可以得到的最大值是多少，在这个地方可以不必担心空格的位置，因为如果错开一个值，要得到最大的长度，那么一定是在之前已求得的子序列中找最大的来-1
if f[i,j]>ans then ans:=f[i,j];
end;
writeln(ans);
end;
begin
init;
readdata;
main;
close(input);
close(output);
end.