NYOJ760-See LCS again，有技巧的暴力！

See LCS again

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述

There are A, B two sequences, the number of elements in the sequence is n、m;

Each element in the sequence are different and less than 100000.

Calculate the length of the longest common subsequence of A and B.

输入

The input has multicases.Each test case consists of three lines;

The first line consist two integers n, m (1 < = n, m < = 100000);

The second line with n integers, expressed sequence A;

The third line with m integers, expressed sequence B;

输出

For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.

样例输入

样例输出

上传者

TC_胡仁东

东哥的题，，TC元老级人物，请收下15级菜鸡的膝盖。

很裸的求LCS。但基于数据大，所以超时的做法不用考虑了。看提交纪律很多MLE的，于是用滚动数组。。WA了。于是在网上找了一种很暴力钻数据空子的做法。详见：http://karsbin.blog.51cto.com/1156716/966387

其实这种做法以前寒假学LCS的时候在网上看到过，当时和小田说了一下，我们都很震惊。但后来被他所举的例子也就是上面博客中提到的例子退化的LCS所推翻了。基于数据水的前提下是可以试试的。一下摘自上面那位大神的博客：

这里也可将其转化为最长递增子序列问题。

举例说明：

A：abdba

B：dbaaba

则1：先顺序扫描A串，取其在B串的所有位置：

2：a(2,3,5) b(1,4) d(0)。

3：用每个字母的反序列替换，则最终的最长严格递增子序列的长度即为解。

替换结果：532 41 0 41 532

最大长度为3.

简单说明：上面的序列和最长公共子串是等价的。

对于一个满足最长严格递增子序列的序列，该序列必对应一个匹配的子串。

反序是为了在递增子串中，每个字母对应的序列最多只有一个被选出。

反证法可知不存在更大的公共子串，因为如果存在，则求得的最长递增子序列不是最长的，矛盾。

最长递增子序列可在O(NLogN)的时间内算出。

配上代码：

const int N=1e5+7;

int c[N],d[N],a[N],b[N],v[N];

int find(int x,int *a,int len)

{

  int l=0,r=len;

  while(l<=r)

  {

      int mid=(l+r)/2;

      if(a[mid]==x) return mid;

      if(a[mid]<x) l=mid+1;

      else r=mid-1;

  }

  return l;

}

void dp(int *a,int k)

{

  int len=0;

  int b[N];

  b[1]=a[0];

  if(k) len=1;

  for(int i=1;i<k;i++)

  {

    if(b[len]<a[i])

      b[++len]=a[i];

      else

      {

          int pos=find(a[i],b,len);

          b[pos]=a[i];

      }

  }

  printf("%d\n",len);

}

int main()

{

    int n,m;

    while(~scanf("%d%d",&n,&m))

    {

        memset(v,0,sizeof(v));

        vector<int>q[N];

        for(int i=0; i<n; i++)

        {

            scanf("%d",&a[i]);

            v[a[i]]=1;

        }

        for(int i=0; i<m; i++)

        {

            scanf("%d",&b[i]);

            if(v[b[i]]) q[b[i]].push_back(i);

        }

        int k=0;

        for(int i=0; i<n; i++)

            if(!q[a[i]].empty())//其实这里就钻了空子，如果一万个1和一万个1超时是必然的。

            {

                for(int j=q[a[i]].size()-1; j>=0; j--)

                    c[k++]=q[a[i]][j];

            }

        //for(int i=0;i<k;i++) printf("%d%c",c[i],i==k-1?'\n':' ');

        dp(c,k);

    }

    return 0;

}

以上是本菜鸡的一点想法，严格来说不够严谨，单纯为了提高题量。。这样是很不好的。

如果路过的大牛有更好的思路，欢迎提出。

巴特西

NYOJ760-See LCS again，有技巧的暴力！

See LCS again

最新文章

热门文章