Loading...

题解--顺序对齐

check评论:1 条 remove_red_eye浏览量:1364 change_historyTags:编程学习笔记
作者 : deco date_range日期 : 2019-07-03

捕获.PNG- 题目描述

考虑两个字符串右对齐的最佳解法。例如,有一个右对齐方案中字符串是$AADDEFGGHC$和$EGGHEADED$
$AAD\_DEFGGHC$
$ADCDE\_\_GH\_$
每一个数值匹配的位置值$2$分,一段连续的空格值$-1$分。所以总分是匹配点的$2$倍减去连续空格的段数,在上述给定的例子中,$6$个位置$(A,D,D,E,G,H)$匹配,三段空格,所以得分$2\times 6+(-1)\times 3=9$,注意,我们并不处罚左边的不匹配位置。若匹配的位置是两个不同的字符,则既不得分也不失分。
请你写个程序找出最佳右对齐方案。

  • 题目分析

方法$1:$令$f[i][j]$表示第一个字符串到了第$i$位,第二个到了第$j$位的最大匹配值

当$s1[i]==s2[j]$时,$f[i][j]=f[i-1][j-1]=2$

当$s1[i]!=s2[j]$时,枚举$k$从$1$到$i$和$j$,从中转移即可,时间复杂度$O(n^3)$

这种方法当数据范围在$3000$时就跑不动了,我们需要优化

方法$2:$继承的思路,我们不需要去枚举前面何处加空格,我们增加半维,即变为$f[i][j][0/1][0/1]$,第一个$0/1$代表第一个串后是否有空格,第二个同理

然后我们每次只需从上一个无空格或已有空格的情况增加空格或延长空格$(s1[i]!=s2[j])$,就可以在$O(n^2)$的复杂度内完成了

  • 代码实现

    /**************************/
    /*It is made by decoration*/
    /*gzzkal   gzzkal   gzzkal*/
    /*It is made by decoration*/
    /**************************/
    #include <bits/stdc++.h>
    using namespace std;
    int dp[3010][3010][2][2],l1,l2;
    char s1[3010],s2[3010];
    int main()
    {
        freopen("tidy.in","r",stdin);
        freopen("tidy.out","w",stdout);
        scanf("%s%s",s1+1,s2+1);
        l1=strlen(s1+1),l2=strlen(s2+1);
        dp[0][0][0][0]=0;
        for(int i=1;i<=l1;i++)
        {
            for(int j=1;j<=l2;j++)
            {
                int t[10];
                for(int k=0;k<=5;k++)
                {
                    t[k]=-1e9;
                }
                if(s1[i]==s2[j])
                {
                    t[0]=dp[i-1][j-1][0][0]+2;
                    t[1]=dp[i-1][j-1][0][1]+2;
                    t[2]=dp[i-1][j-1][1][0]+2;
                }
                else
                {
                    t[3]=dp[i-1][j-1][0][0];
                    t[4]=dp[i-1][j-1][0][1];
                    t[5]=dp[i-1][j-1][1][0];
                }
                t[6]=dp[i][j-1][0][0]-1;
                t[7]=dp[i][j-1][1][0];
                t[8]=dp[i-1][j][0][0]-1;
                t[9]=dp[i-1][j][0][1];
                for(int k=0;k<=5;k++)
                {
                    dp[i][j][0][0]=max(dp[i][j][0][0],t[k]);
                }
                dp[i][j][1][0]=max(t[6],t[7]);
                dp[i][j][0][1]=max(t[8],t[9]);
            }
        }
        cout<<max(dp[l1][l2][0][0],max(dp[l1][l2][0][1],dp[l1][l2][1][0]));
    }

仅有一条评论

正在回复给  
去登陆?

   点击刷新验证码

    被lhy吊打
    被lhy吊打
    2019 - 07 - 05 16 : 41

    orz

标签云

文章留名

被lhy吊打
被lhy吊打