SPOJ 3048 - DNA Sequences LCS
2024-10-15 16:14:47
给出两个字符串(不长于1000),求最长公共子序列,要求:从每个串中取必须取连续k (1<=k<=100)个数
【LCS】一开始自己想用DP加一维[len]用来表示当前已经取了连续len个值,但是1000*1000*100肯定超时,而且这道题的时限779ms是什么鬼
然后想求LCS有没有像LIS一样优化到nlogn的算法,百度一下,还真有【戳这里跳转】,但是基于这个算法来求这道题始终没有什么思路。
还是回到原点设dp[i][j]为第一个字符串到第i位,第二个字符串到第j位,的最大匹配数
不能匹配的时候:dp[i][j]=max( dp[i-1][j] , dp[i][j-1] )
可以匹配的时候:dp[i][j]=max( dp[i][j] , dp[i-p][j-p]+p ) 其中p>=k
【代码链接】
#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<vector>
#include<queue>
#include<string>
#include<sstream>
#define eps 1e-9
#define ALL(x) x.begin(),x.end()
#define INS(x) inserter(x,x.begin())
#define FOR(i,j,k) for(int i=j;i<=k;i++)
#define MAXN 1005
#define MAXM 40005
#define INF 0x3fffffff
using namespace std;
typedef long long LL;
int i,j,k,n,m,x,y,T,ans,big,cas,num,len;
bool flag;
char a[],b[];
int dp[][],lena,lenb,p;
int main()
{
while(scanf("%d",&k),k)
{
scanf("%s",a);lena=strlen(a);
scanf("%s",b);lenb=strlen(b);
memset(dp,,sizeof(dp));
for (i=;i<=lena;i++)
{
for (j=;j<=lenb;j++)
{
dp[i][j]=max(dp[i][j-],dp[i-][j]);
for (p=; i-p>= && j-p>= && a[i-p]==b[j-p] ; p++)
{
if (p>=k)
{
dp[i][j]=max(dp[i][j],dp[i-p][j-p]+p);
}
}
}
}
printf("%d\n",dp[lena][lenb]);
}
return ;
}
最新文章
- Python基础面向对象成员
- 决策树的python实现
- 【CodeForces 604B】F - 一般水的题1-More Cowbe
- View的缩放操作--CGAffineTransformMakeScale:
- JAVA中抽象类的一些总结
- ionic cordova file download and load
- gitbook 制作 beego 参考手册
- js与jquery获取父元素,删除子元素的不同方法
- RHEL4 i386下安装rdesktop【原创】
- rsyslog+LogAnalyzer 日志收集
- HDU Group
- gRPC官方快速上手学习笔记(c#版)
- VS背景设置
- Spring监听,ApplicationListener
- pt站 扫盲贴 面向小白
- 图中最短路径的算法--dijiska算法C语言实现
- 软件工程_1st weeks
- python全栈开发知识点补充for else和while else如果不是除正常以外的其他方式退出循环,那么else语句就会被执行。
- HDU2955 01背包
- 使用 restTemplate 实现get/post 请求