The main idea of the topic : Given n The number and two lengths are n*5 Sequence , Every number happens to be 5 Time , Find the... Of two sequences LCS

n<=20000. The length of the sequence is 10W. Simple O(n^2) It's bound to time out

So we think about LCS Some properties of

LCS The decision +1 Is the condition of a[i]==b[j] So we recorded a Of every number in the sequence 5 A place

Sweep it b[i] For each of these b[i] find b[i] stay a Medium 5 A place this 5 Every one of the positions f[pos] Values can be b[i] to update So I found f[1] To f[pos-1] The maximum of +1 to update f[pos] Can

This is maintained with a tree array Time complexity O(nlogn)

A very difficult question It's just not hard to write

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200200
using namespace std;
int n,ans,a[M*5],b[M*5],c[M*5],f[M*5],pos[M][6];
void Update(int x,int y)
{
for(;x<=n*5;x+=x&-x)
c[x]=max(c[x],y);
}
int Get_Ans(int x)
{
int re=0;
for(;x;x-=x&-x)
re=max(re,c[x]);
return re;
}
int main()
{
int i,j;
cin>>n;
for(i=1;i<=n*5;i++)
{
scanf("%d",&a[i]);
pos[ a[i] ][ ++pos[a[i]][0] ]=i;
}
for(i=1;i<=n*5;i++)
scanf("%d",&b[i]);
for(i=1;i<=n*5;i++)
{
for(j=5;j;j--)
{
int k=pos[b[i]][j];
f[k]=max( f[k] , Get_Ans(k-1)+1 );
Update(k,f[k]);
ans=max(ans,f[k]);
}
}
cout<<ans<<endl;
}

BZOJ 1264 AHOI2006 Gene matching Match Dynamic programming + Tree array of more related articles

  1. bzoj 1264 [AHOI2006] Gene matching Match dp + Tree array

    Ideas : It's hard to imagine , Considering that there should be only... From each number 5 Start with a number , But I don't know how to write it .. First of all, we classify the first string according to the type of number , In each category there are 5 individual , Then add the numbers in the second string one by one , If a member of the third party i ...

  2. BZOJ 1264: [AHOI2006] Gene matching Match DP_ Tree array _LCS turn LIS

    Because there are duplicate numbers , We base it on a sequence , In another sequence, the subscript of each number in the first sequence is the corresponding value of each number in this sequence . Pay attention to is , When splitting values, they are ranked from large to small according to the position in the first sequence , You can only choose one . The longest ascending subsequence on the last side ...

  3. BZOJ1264 [AHOI2006] Gene matching Match Dynamic programming Tree array

    Welcome to visit ~ The source of the original text is —— Blog Garden -zhouzhendong Go to the blog Garden to see the solution Subject portal - BZOJ1264 Topic summary Give two lengths of 5*n Sequence , In each sequence , Yes 1~n various 5 individual . Find the longest common subsequence length . ...

  4. 【BZOJ1264】[AHOI2006] Gene matching Match DP+ Tree array

    [BZOJ1264][AHOI2006] Gene matching Match Description Gene matching (match) Kaka had a dream last night that he and coco came to another planet , Life on this planet DNA The sequence consists of innumerable bases ...

  5. bzoj 1264 [AHOI2006] Gene matching Match(DP+ Tree array )

    1264: [AHOI2006] Gene matching Match Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 793  Solved: 503[Submit][S ...

  6. BZOJ 1264: [AHOI2006] Gene matching Match Tree array +DP

    1264: [AHOI2006] Gene matching Match Description Gene matching (match) Kaka had a dream last night that he and coco came to another planet , Life on this planet DNA The sequence is made up of innumerable bases ( The earth ...

  7. BZOJ 1264: [AHOI2006] Gene matching Match( LCS )

    Maximum sequence length 2w * 5 = 10w, O(n²) Of LCS Meeting T.. LCS Only when a[i] == b[j] when , To update the answer , We can record n The number that appears in the first sequence 5 A place , Then scan the second sequence from left to right ...

  8. bzoj 1264: [AHOI2006] Gene matching Match

    1264: [AHOI2006] Gene matching Match Description Gene matching (match) Kaka had a dream last night that he and coco came to another planet , Life on this planet DNA The sequence is made up of innumerable bases ( The earth ...

  9. bzoj 1264: [AHOI2006] Gene matching Match ( Tree array optimization dp)

    link :https://www.lydsy.com/JudgeOnline/problem.php?id=1264 Ideas : n The size is 20000*5, And general dp The complexity of finding the longest common subsequence is n*n Of , So I ...

Random recommendation

  1. sparklyr package -- Realization R And Spark Interface

    1.sparklyr Package introduction Rstudio Issued by the company sparklyr The package has the following functions : Realization R And Spark The connection of : sparklyr The package provides a complete dplyr Back end , Can be screened and aggregated Spark Data sets , Pick up ...

  2. iOS And PJSIP Static library compilation ( Two )

    Let's pick up the book : The last one has been compiled PJsip This time, let's do some actual combat You don't have to make any changes after the last compilation, because ios All the libraries on the platform support . Open the project   find pjsip- apps/src/pjsua/ios/ipjsua ...

  3. windows Next Qt5.1.0 To configure android Environment building good

    1. First, download the software that needs to be configured : 1>Qt 5.1.0 for Android (Windows 32-bit, 716 MB)(Info) Download address : http://qt-project.org/ ...

  4. BZOJ 2561 Minimum spanning tree ( Maximum flow )

    Topic link :http://61.187.179.132/JudgeOnline/problem.php?id=2561 The question : Given a connected undirected graph with positive weight G= (V,E), among N=|V|,M=|E|,N ...

  5. nyoj 73 Than the size

    Click to open the link Than the size The time limit :3000 ms  |  Memory limit :65535 KB difficulty :2 describe Here are two big numbers , Can you judge the size of their two numbers ? such as 123456789123456789 Be greater than ...

  6. How to decode Adobe Acrobat9 pro?( turn )

    terms of settlement : 1. To C:\Program Files\Common Files\Adobe\Adobe PCD\cache Found under folder Cache.db, And delete this file . 2. open Adobe Acr ...

  7. Android The function of regular reminder is realized every day

    android To achieve the function of timing, we must use the alarm related technology , that android The alarm implementation is based on AlarmManager This class of , First of all, let's take a look at some of its main methods . open AlarmManager Of ...

  8. hadoop Source code compilation

    Why compile on your own hadoop Source code , It's often because of the official hadoop The distribution is based on 32 Bit operating system , In operation hadoop Occurs when warn.   Prepare the software : 1)JDK 2)Hadoop Source code 3)Maven 4 ...

  9. Add local jar Package to local Maven Warehouse and in Maven Search the repository for the ones you want to add jar package

    I'm learning today Memacached When , take java_memcached-release download , To use maven To integrate the relevant jar package ,Memcached Of jar The package is as follows : java_memcached-r ...

  10. 201521123026《Java Programming 》 The first 8 Weekly learning summary

    1. Summary of this chapter 1.1 In the way you like ( Mind mapping or something ) Summarize the related contents of set and generics . 2. Written work Q1.1.List Deletion of specified elements in ( subject 4-1) 1.1 Summary of the experiment answer : 1. adopt equals ...