codevs 2185 最长公共上升子序列--nm的一维求法

2185 最长公共上升子序列

 时间限制: 1 s

 空间限制: 32000 KB

 题目等级 : 钻石 Diamond

题目描述 Description

熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们要研究最长公共上升子序列了。
小沐沐说，对于两个串A，B，如果它们都包含一段位置不一定连续的数字，且数字是严格递增的，那么称这一段数字是两个串的公共上升子串，而所有的公共上升子串中最长的就是最长公共上升子串了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子串。不过，只要告诉奶牛它的长度就可以了。

输入描述 Input Description

第一行N，表示A，B的长度。
第二行，串A。
第三行，串B。

输出描述 Output Description

输出长度。

样例输入 Sample Input

4
2 2 1 3
2 1 2 3

样例输出 Sample Output

2

数据范围及提示 Data Size & Hint

1<=N<=3000，A，B中的数字不超过maxlongint

/*思路：f[]数组里面储存着到b的第i项，a从1--n的且以b[i]结尾的最长公共上升子序列长度，
 问题一： dp方程说明：if(a[i]>b[j]&&maxx<f[j])更新可以用于更新b序列与a序列前i位的最长长度的最大值 
                    maxx=f[j];
                  if(a[i]==b[j]) f[j]=maxx+1;因为j是内循环，所以如果maxx被更新了，则现在的b[j]是等于a[i]，一定比更新maxx的bj大，所以可以直接加。 
问题二： 为什么可以改为一维？：类似于背包问题，假如用f[i][j]表示到了a的第i项（不一定为ai结尾），以b的第j项结尾的最长长度，那么 f[i][j]，如果ai!=bj,那么f[i-1][j]就是最佳选择，而且一定比f[i-2][j]优，而当ai==bj的时候，我们用maxx更新f[i][j]，与之前的无关，那么可见F[i][j]只与i-1的值有关，那么就可以用一唯数组了。 
      */
#include<iostream>
using namespace std;
#include<cstdio>
const int N=3001;
int a[N],b[N],f[N],maxx;
int main()
{
    ios::sync_with_stdio(false);
    int n;
    cin>>n;
    for(int i=1;i<=n;++i)
    cin>>a[i];
    for(int i=1;i<=n;++i)
    cin>>b[i];
    for(int i=1;i<=n;++i)
      {
          maxx=0;
          for(int j=1;j<=n;++j)
          {
              if(a[i]>b[j]&&maxx<f[j])
              maxx=f[j];
              if(a[i]==b[j]) f[j]=maxx+1;
          }
      }
    maxx=0;
    for(int i=1;i<=n;++i)/*因为对于f[]数组我们是规定了结尾，所以f[n]不一定是最优值，所以要全搜索一次*/
    maxx=max(f[i],maxx);
    cout<<maxx<<endl;
    return 0;
}