首页 > > 程序设计 > C/C++ >

洛谷P1852 奇怪的字符串

2018-06-17 21:31:30来源：未知阅读 ()

题目描述

输入两个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:

 1                         #include<cstdio>
 2 #include<cstring>
 3 using namespace std;
 4 const int MAXN=10001;
 5 inline char nc()
 6 {
 7     static char buf[MAXN],*p1=buf,*p2=buf;
 8     return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
 9 }
10 inline int read()
11 {
12     char c=nc();int x=0,f=1;
13     while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
14     while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
15     return x*f;
16 }
17 inline int work(int x)
18 {
19     int ans=0;
20     for(int i=1;i<x;i++)   
21         if(x%i==0)  ans+=i;
22     return ans;
23 }
24 int dp[MAXN];//i位置的长度
25 int f[MAXN];//i位置所对应的位置 
26 char a[MAXN],b[MAXN];
27 int main()
28 {
29     #ifdef WIN32
30     freopen("a.in","r",stdin);
31     #else
32     #endif
33     scanf("%s",a+1);
34     scanf("%s",b+1);
35     int la=strlen(a+1),lb=strlen(b+1);
36     for(int i=1;i<=lb;i++)
37     {
38         dp[i]=dp[i-1];
39         f[i]=f[i-1];
40         for(int j=f[i-1]+1;j<=la;j++)
41         {
42             if(b[i]==a[j])
43             {
44                 dp[i]=dp[i]+1;
45                 f[i]=j;
46                 break;
47             }
48         }
49     }
50     if(dp[lb]==3&&lb>=16)    printf("16");
51     else printf("%d",dp[lb]);
52     return 0;
53 } 
54

xjb贪心

正解是裸地LCS

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

数据太水了没办法

注意滚动数组

                        #include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN=10001;
inline char nc()
{
    static char buf[MAXN],*p1=buf,*p2=buf;
    return p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
    char c=nc();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=nc();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';c=nc();}
    return x*f;
}
inline int work(int x)
{
    int ans=0;
    for(int i=1;i<x;i++)   
        if(x%i==0)  ans+=i;
    return ans;
}
int dp[3][MAXN];//i位置的长度
char a[MAXN],b[MAXN];
int main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #else
    #endif
    scanf("%s",a+1);
    scanf("%s",b+1);
    int la=strlen(a+1),lb=strlen(b+1);
    for(int i=1;i<=la;i++)
        for(int j=1;j<=lb;j++)
            if(a[i]==b[j])
                dp[i^1][j]=dp[(i-1)^1][j-1]+1;
            else dp[i^1][j]=max(dp[(i-1)^1][j],dp[i^1][j-1]);
    printf("%d",dp[la^1][lb]);
    return 0;
}