首页 > 代码库 > 顺序对齐

顺序对齐

http://zsyz.openjudge.cn/dp/18/
总时间限制: 
1000ms
 
内存限制: 
102400kB
描述

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

AAD_DEFGGHC          

ADCDE__GH_          

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

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

输入
输入文件包含两行,每行一个字符串,最长50个字符。字符全部是大字字母。
输出
一行,为最佳对齐的得分。
样例输入
AADDEFGGHCADCDEGH
样例输出
9

f[i][j] 表示匹配到第一个串前i个,第二个串前j个的最大得分
有4中决策:
匹配 f[i][j]=f[i-1][j-1]+2
第一个串位置i加空格: f[i][j]=max(f[i][j],f[k][j]-1) 1<k<i
第二个串位置j加空格: f[i][j]=max(f[i][j],f[i][k]-1) 1<k<j
不匹配但不空格 f[i][j]=max(f[i][j],f[i-1][j-1])

题目中不处罚左边不匹配位置,
若左边都不匹配,如果处罚,f为负数
但因为初始值为0,取大还是0,相当于不处罚
#include<cstdio>#include<cstring>#include<algorithm>using namespace std;char a[51],b[51];int  f[51][51],l1,l2;int main(){    scanf("%s%s",a+1,b+1);    l1=strlen(a+1); l2=strlen(b+1);    for(int i=1;i<=l1;i++)     for(int j=1;j<=l2;j++)      {           if(a[i]==b[j]) f[i][j]=f[i-1][j-1]+2;           for(int k=1;k<i;k++) f[i][j]=max(f[i][j],f[k][j]-1);           for(int k=1;k<j;k++) f[i][j]=max(f[i][j],f[i][k]-1);           f[i][j]=max(f[i][j],f[i-1][j-1]);      }     printf("%d",f[l1][l2]);}

 

 

顺序对齐