洛谷P1852 奇怪的字符串

题目描述

输入两个01串，输出它们的最长公共子序列的长度

输入输出格式

输入格式：

一行，两个01串

输出格式：

最长公共子序列的长度

输入输出样例

输入样例#1：复制

01010101010 00000011111

输出样例#1：复制

说明

01串长度≤10000

数据好水啊

一开始想了一个dp[i]表示以b中到达i位置最长的LCS，f[i]表示他的位置，然后转移就好，不过这样只能处理LCS是从1开始的情况

比如

01110

101100这个数据就过不去了，

然而。。

我得了90.。。。。。。。

后来加了个特判就A了，

时间复杂度严格O(la+lb)

速度保证全洛谷rank1:joy:

                         #include<cstdio>

 #include<cstring>

 using namespace std;

 const int MAXN=;

 inline char nc()

 {

     static char buf[MAXN],*p1=buf,*p2=buf;

     return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;

 }

 inline int read()

 {

     char c=nc();int x=,f=;

     while(c<''||c>''){if(c=='-')f=-;c=nc();}

     while(c>=''&&c<=''){x=x*+c-'';c=nc();}

     return x*f;

 }

 inline int work(int x)

 {

     int ans=;

     for(int i=;i<x;i++)

         if(x%i==)  ans+=i;

     return ans;

 }

 int dp[MAXN];//i位置的长度

 int f[MAXN];//i位置所对应的位置

 char a[MAXN],b[MAXN];

 int main()

 {

     #ifdef WIN32

     freopen("a.in","r",stdin);

     #else

     #endif

     scanf("%s",a+);

     scanf("%s",b+);

     int la=strlen(a+),lb=strlen(b+);

     for(int i=;i<=lb;i++)

     {

         dp[i]=dp[i-];

         f[i]=f[i-];

         for(int j=f[i-]+;j<=la;j++)

         {

             if(b[i]==a[j])

             {

                 dp[i]=dp[i]+;

                 f[i]=j;

                 break;

             }

         }

     }

     if(dp[lb]==&&lb>=)    printf("");

     else printf("%d",dp[lb]);

     return ;

 }

xjb贪心

正解是裸地LCS

不过按理说O(n^2)的应该过不去

数据太水了没办法

注意滚动数组

                        #include<cstdio>

#include<cstring>

#include<algorithm>

using namespace std;

const int MAXN=;

inline char nc()

{

    static char buf[MAXN],*p1=buf,*p2=buf;

    return p1==p2&&(p2=(p1=buf)+fread(buf,,MAXN,stdin),p1==p2)?EOF:*p1++;

}

inline int read()

{

    char c=nc();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=nc();}

    while(c>=''&&c<=''){x=x*+c-'';c=nc();}

    return x*f;

}

inline int work(int x)

{

    int ans=;

    for(int i=;i<x;i++)

        if(x%i==)  ans+=i;

    return ans;

}

int dp[][MAXN];//i位置的长度

char a[MAXN],b[MAXN];

int main()

{

    #ifdef WIN32

    freopen("a.in","r",stdin);

    #else

    #endif

    scanf("%s",a+);

    scanf("%s",b+);

    int la=strlen(a+),lb=strlen(b+);

    for(int i=;i<=la;i++)

        for(int j=;j<=lb;j++)

            if(a[i]==b[j])

                dp[i^][j]=dp[(i-)^][j-]+;

            else dp[i^][j]=max(dp[(i-)^][j],dp[i^][j-]);

    printf("%d",dp[la^][lb]);

    return ;

}

巴特西

洛谷P1852 奇怪的字符串

题目描述

输入输出格式

输入输出样例

说明

最新文章

热门文章