`
java-mans
  • 浏览: 11339241 次
文章分类
社区版块
存档分类
最新评论

hdu_1159 LCS

 
阅读更多

看到那些内存几千k的代码我就蛋疼~~一维数组不就够了吗?

#include<iostream>
#include<string>
using namespace std;
char s[1024];
int dp[1024];
string a,b;
int temp,tmax,t2;
inline void init()
{
    memset(dp,0,sizeof(dp));
    return ;
}
void dpstart()
{
    init();
    for(int i=0;i<a.length();i++)
    {
        temp=0;
        for(int j=0;j<b.length();j++)
        { 
            if(a[i]==b[j])
            {
                t2=dp[j];
                dp[j]=temp+1;
                if(t2 > temp)
                {
                    temp=t2;
                }
            }
            else
            {
                if(dp[j]>temp)
                {
                    temp=dp[j];
                }
            }
        }       
    }   
    tmax=0; 
    for(int i=0;i<b.length();i++)
    {
        if(dp[i]>tmax)
        {
            tmax=dp[i];
        }
    }
    return ;
}
int main()
{
    while(scanf("%s",&s)!=EOF)
    {
        a=s;
        if(scanf("%s",&s)==EOF)
        {
            break;
        }
        else
        {
            b=s;
        }
        dpstart();
        printf("%d\n",tmax);
    }    
    return 0;
}


分享到:
评论

相关推荐

Global site tag (gtag.js) - Google Analytics