洛谷P1852 奇怪的字符串
题目描述
输入两个01串，输出它们的最长公共子序列的长度
输入输出格式
输入格式：
一行，两个01串
输出格式：
最长公共子序列的长度
输入输出样例
输入样例#1：
01010101010 00000011111输出样例#1：
6说明
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 正解是裸地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;
}
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2017-11-28 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录