SPOJ 3048 – DNA Sequences LCS

给出两个字符串（不长于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 ;
}