HDU 4512 最长公共上升子序列

各种序列复习：

（1）最长上升子序列。

1、这个问题用动态规划就很好解决了，设dp[i]是以第i个数字结尾的上升子序列的最长长度。那么方程可以是dp[i]=max(dp[j]+1)。（j<i）。复杂度为O(n^2);

2、另外有一个该经典问题的O(nlogn)算法。

　　首先知道，当求dp[i]时，如果出现a[k]<a[j],而dp[k]=dp[j]时，应当优先选k吧。那么，既然每次选的都是较小，就可以把字符串按照dp[t]=k这个子序列长度分类。当同样dp[t]=k时，记录下该长度的最小的a[p]，设为数组d[k]。注意到d数组是单调不减的。为什么呢？因为假设当前是长度p，记录的位置就为d[p]，如果出现d[q]>d[p]，q<p，干脆就让以d[p]结尾的子序代替前面的。

　　于是有这个特点：

　　A、d[1]<=d[2]<=.......

　　那么，在每次更新dp[i]时，对于字符a[i]，只需找出比它小的最大的k，使d[k]<a[i]，不就可以了吗。然后更新dp[i]。对于查找，由于单调，很明显可以使用二分查找。

　　对于一个比较巧妙的写法。

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 using namespace std;

 const int N = ;

 int a[N];       //a[i] 原始数据

 int d[N];       //d[i] 长度为i的递增子序列的最小值  

 int BinSearch(int key, int* d, int low, int high)

 {

     while(low<=high)

     {

         int mid = (low+high)>>;

         if(key>d[mid] && key<=d[mid+])

             return mid;

         else if(key>d[mid])

             low = mid+;

         else

             high = mid-;

     }

     return ;

 }  

 int LIS(int* a, int n, int* d)

 {

     int i,j;

     d[] = a[];

     int len = ;        //递增子序列长度

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

     {

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

             j = ++len;

         else

             j = BinSearch(a[i],d,,len) + ;

         d[j] = a[i];

     }

     return len;

 }  

 int main()

 {

     int t;

     int p;

     scanf("%d",&t);

     while(t--)

     {

         scanf("%d",&p);

         for(int i = ; i <= p; i++)

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

         printf("%d\n",LIS(a,p,d));

     }

     return ;

 }

(2)最长公共子序列。

设dp[i][j]是第一个字符串以第i个结尾，第二个字符串以第j个结尾的长度。

　　那么就有dp[i][j]=max{dp[i-1][j],dp[i][j-1],dp[i-1][j-1]}。前两种情况针对a[i]!=a[j]的，后一种是针对相等的。

(3)最长公共上升子序列。

我介绍一种O(N(M^2))的算法，它将是我们向O(NM)进步的阶梯。我们设F[j]为必选择B[j]为末尾时的最长。。。子序列（懒得打），那么F[j] = Max{F[k]}+1，并且通过设置一个i变量来枚举A[i]。

 var

     f       : array[..] of integer;

     ans     : integer;

 procedure work2();

 var

     i,j,k:integer;

 begin

     for i:=  to n do

         for j:=  to m do

             if a[i] = b[j] then

                 for k:=  to j- do

                     if b[k] < b[j] then

                         if f[j] < f[k]+ then

                             f[j]:=f[k]+;

     for i:=  to m do

         if ans < f[i] then

             ans:=f[i];

 end;

此时我们把空间降到了一维。解释一下，k循环下面比较时，B[k]所对应的A[?]一定在A[i]以前，而k也小于j，这就保证了解的合法性。但注意到其中的k循环，这实际上是用来找最大值用的。那么我们想，为什么不把最大只保存起来呢？i循环没结束时不断更新这个k值就行了啊。那么下面的算法就出来了：

procedure work;

var

    i,j,k:integer;

begin

    for i:=  to n do

        begin

            k:=;

            for j:=  to m do

                begin

                    if a[i] = b[j] then

                        if f[j] < f[k]+ then

                            f[j]:=f[k]+;

                    if a[i] > b[j] then

                        if f[k] < f[j] then

                            k:=j;                  // 更新新的k

                end;

        end;

    for i:=  to m do

        if ans < f[i] then

            ans:=f[i];

end;

其实，对于上面的更新保存最大值的操作，为什么是可行的呢？

要知道，更新DP数组f是在a[i]==b[j]时才进行的，因为f数组定义的是以b[j]为结尾的最长序列。那么，由于是上升的，则必定是在结尾的字符之前b[k]<a[i]吧？那么，在扫描的过程中，就可以当满足

f[k] < f[j]时更新k了。

 对于HDU 4512这道题，也就是最长公共上升子序列的模型。我以两个序列来模拟，一个顺序一个逆序。在代码中可以知道，对于以b[j]为结束序列，在最外层循环到i时，内层循环最多只能到n-i+1，为什么呢？因为两个序列是互逆的，当超出这个值时，它们之前的序列就可能交叉或重叠。当a[n-i+1]==b[j]&&n-不+1==j时，序列最长应该是奇数的。在求解过程中找出最长序列即可。

 #include <iostream>

 #include <cstdio>

 #include <algorithm>

 #include <cstring>

 using namespace std;

 int num1[],num2[];

 int f[];

 int main(){

     int T,n;

     scanf("%d",&T);

     while(T--){

         scanf("%d",&n);

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

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

             num2[n-i+]=num1[i];

         }

         memset(f,,sizeof(f));

         int ans=;

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

             int k=;

             for(int j=;j<=n-i+;j++){

                 if(num2[i]==num1[j]){

                     if(f[j] < f[k]+)

                     f[j]=f[k]+;

                     if(j==n-i+)

                     ans=max(ans,*f[j]-);

                     else {

                         ans=max(ans,*f[j]);

                     }

                 }

                 if(num2[i]>num1[j]){

                     if(f[k]<f[j])

                     k=j;

                 }

             }

         }

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

     }

     return ;

 }

巴特西

HDU 4512 最长公共上升子序列

最新文章

热门文章