首页 > 代码库 > 顺序对齐
顺序对齐
- 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]);}
顺序对齐
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。