【♂Not The Triumph♂O(∩_∩)O哈哈~But The Struggle♂】

竞赛决不是捷径,它只是另一种艰辛的生活方式。得到与失去,只有时间会去评判;成功与失败,只有历史能去仲裁。我不会永远成功,正如我不会永远失败一样

  C++博客 :: 首页 :: 联系 ::  :: 管理
  6 Posts :: 239 Stories :: 25 Comments :: 0 Trackbacks

常用链接

留言簿(7)

我参与的团队

搜索

  •  

积分与排名

  • 积分 - 104228
  • 排名 - 233

最新评论

阅读排行榜

评论排行榜

【问题描述】

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

AAD_DEFGGHC
ADCDE__GH_

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

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

 

【输入文件】

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

【输出文件】

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

 【输入输出样例】

输入:
AADDEFGGHC
ADCDEGH

输出:
9

【参考程序】:

#include<cstring>
#include
<cstdio>
#include
<cstdlib>
#include
<iostream>
using namespace std;
string s,s1,s2;
long f[60][60];
long n,m,max1,max2;
long find_max(long x,long y)
{
    
if (x>y) return x;
    
else return y;
}
int main()
{
    freopen(
"align.in","r",stdin);
    freopen(
"align.out","w",stdout);
    s1
=s2=" ";
    getline(cin,s);
    n
=s.length();
    
for (int i=n-1;i>=0;i--) s1+=s[i];
    getline(cin,s);
    m
=s.length();
    
for (int i=m-1;i>=0;i--) s2+=s[i];
    
for (int i=0;i<=n;i++)
        
for (int j=0;j<=m;j++)
            f[i][j]
=-9999999;
    
for (int i=1;i<=n;i++) f[i][0]=-1;
    
for (int i=1;i<=m;i++) f[0][i]=-1;
    f[
0][0]=0;
    max2
=-1000;
    
for (int i=1;i<=n;i++)
        
for (int j=1;j<=m;j++)
        {
            max1
=-1000;
            f[i][j]
=f[i-1][j]-1;
            
if (s1[i]==s2[j]) max1=f[i-1][j-1]+2;
            
else max1=f[i-1][j-1];
            
for (int k=1;k<=i-1;k++
                 max1
=find_max(max1,f[k][j]-1);
            
for (int k=1;k<=j-1;k++
                max1
=find_max(max1,f[i][k]-1);
            f[i][j]
=find_max(f[i][j],max1);
            max2
=find_max(max2,f[i][j]);
        }
    printf(
"%ld\n",max2);
    system(
"pause");
    
return 0;
}
posted on 2009-04-09 20:02 开拓者 阅读(873) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理