最长公共上升子序列
熊大妈的奶牛在小沐沐的熏陶下开始研究信息题目。
小沐沐先让奶牛研究了最长上升子序列，再让他们研究了最长公共子序列，现在又让他们研究最长公共上升子序列了。
小沐沐说，对于两个数列 A 和 B，如果它们都包含一段位置不一定连续的数，且数值是严格递增的，那么称这一段数是两个数列的公共上升子序列，而所有的公共上升子序列中最长的就是最长公共上升子序列了。
奶牛半懂不懂，小沐沐要你来告诉奶牛什么是最长公共上升子序列。
不过，只要告诉奶牛它的长度就可以了。
数列 A 和 B 的长度均不超过 3000。
输入格式
第一行包含一个整数 N，表示数列 A，B的长度。
第二行包含 N 个整数，表示数列 A。
第三行包含 N 个整数，表示数列 B。
输出格式
输出一个整数，表示最长公共上升子序列的长度。
数据范围
1≤N≤3000,序列中的数字均不超过 231−1。
输入样例：
4
2 2 1 3
2 1 2 3
输出样例：
2
好吧，我承认看到题就直接懵逼了…….
我们之前做过最长上升子序列和最长公共子序列。这里就简单回顾一下一些基本的参数。
LIS：
状态表示：dp[i] 表示从1到i的序列中，且是以i结尾的，最长的上升子序列的长度。
状态属性：max
base case：dp[i] = 1 ;
状态转移：用i做一次遍历，然后用j往前进行遍历，如果遇到符合要求的，继续找最大值即可。
for(int i = 1 ; i <= n ; ++ i)
{
dp[i] = 1 ;
for(int j = i-1 ; j >= 0 ; --j)
{
if(a[i] > a[j])
dp[i] = max(dp[i] , dp[j] + 1) ;
}
}
LCS：
状态表示：dp[i] [j] 表示a串的1-i， 到b串的1-j，中最长的公共子序列，不一定要是以j结尾。
状态属性：max
base case：dp[i] [0] = 0 ; dp[0] [i] = 0 ;
状态转移：
if 相等 dp[i] [j] = dp[i-1] [j-1] + 1 ;
else dp[i] [j] = max(dp[i-1] [j] , dp[i] [j-1]) ;
for(int i = 1 ; i <= n ; ++i)
{
for(int j = 1 ; j <= n ;++ j)
{
if(a[i] == b[j])
{
f[i][j] = f[i-1][j-1] + 1 ;
}
else
{
f[i][j] = max(f[i-1][j] , f[i][j-1]) ;
}
}
}
好，其实这一题就是上述两题的融合。
我们学着来自行分析一下基本参数：
状态表示：dp[i] [j] 表示a串1-i ， b串1-j， 且b串以j结尾的序列的包含的最长公共上升子序列。
(为什么非要是以j结尾呢？不以任何结尾行吗)（为什么不以i结尾？）
状态属性：max
base case：同LCS，但是申请全局变量了，就不需要显性的申明了。
状态转移：
if 相等 由于j是定位符的特性，找到倒数第二个满足最长公共上升子序列的j的下标，要以此来进行转移。
贴个代码：
#include
using namespace std ;
const int N = 3010 ;
int a[N] , b[N] ;
int f[N][N] ;
int main()
{
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)
{
for(int j = 1 ; j <= n ; ++ j)
{
f[i][j] = f[i-1][j] ;
if(a[i] == b[j])
{
f[i][j] = max(f[i][j] , 1) ;
for(int k = 1 ; k < j ; ++ k)
{
if(b[k] < b[j])
{
f[i][j] = max(f[i][j] , f[i-1][k] + 1) ;
}
}
}
}
}
int res = 0 ;
for(int i = 1 ; i <= n ; ++i)
{
res = max(res , f[n][i]) ;
}
cout << res << endl ;
return 0 ;
}
这段代码是完全根据我们的思路来走的，属于是最朴素的代码，我们可以看到有三层循环。数据范围是在1000左右的，最后应该会TLE。
所以，我们如何才能有三轮优化成两轮？？？
明天再更….. 今天累了
——————-10-13 再更————————————————————————————————————————–
昨天实在没有领悟到精髓之处，在经历了这一道题对我的知识框架的冲击与重建之后，我开始寻找y总的dp分析法与我自己总结的方法的共同之处，现在还在领悟之中。
y总的分析法，主要着重于集合分析，主要着重于状态转移的时候，可以将集合分成两个不重不漏的集合，然后对每个集合进行细分，每个集合取自己的状态属性，然后大的方面再取两个集合的总属性。
今天再次看到这道题感觉又有了新的思路：
又再次重温了一下LIS与LCS的例题，想要通过这两道题目找到一些新的思路。
我们可以看出来，LCIS这道题在表示的过程中，确实是借鉴了前两道题，既有LIS的以i结尾的设法，也有LCS的模糊性设法。
整个dp的状态转移的过程其实就是以LCS作为前提，在进入前提之后，在去用LIS的方法去找到符合要求的状态表示 。 同时注意一下，转移时候的一些细节即可。至于y总说的，将集合凭借用a[i] 与不用来进行划分可以理解，其实就是我说的，思考来源的过程，考虑a[i]其实就是自身较大，不考虑其实就是通过自身之前的状态进行转移，只能说我只能凭借我对这道题目的理解来强行解释这种思路，看起来可以解释的通，但是却没有找到一个可以让自己先手就立即想到的理由。
#include
using namespace std ;
const int N = 3010 ;
int a[N] , b[N] ;
int f[N][N] ;
int main()
{
int n ;
cin >> n ;
int res = 0 ;
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)
{
for(int j = 1 ; j <= n ; ++j)
{
f[i][j] = f[i-1][j] ; //便于迭代，要不然没有东西迭代了
if(a[i] == b[j]) //进入LCS的前提
{
f[i][j] = max(f[i][j] , 1) ;
for(int k = 1 ; k < j ; ++k ) //LIS的模式
{
if(b[k] < b[j])
f[i][j] = max(f[i][j] , f[i-1][k] + 1) ;
}
}
res = max(res , f[i][j]) ;
}
}
cout << res << endl ;
return 0 ;
}
好吧，感觉像是理解了，但是应该是未完全理解。之后等自己再继续刷题，说不定过一段时间之后就成了显然了>_<.
好的，主要思路就是上述，但是这题的数据是3000，如果暴力的话，没话说，直接超时。我们想着可以进行优化，但是空间上我们不用去管它。
对于时间上的优化，我们一般采用的是等价转换，单纯从代码上进行修改。
想要把时间复杂度优化成2，所以就要想办法将最后一个循环灭了。最后一个循环主要是找到j以前的状态找到符合要求的然后进行转移。
那我们有没有一种可能，提前就可以将这一个最大值就直接储存起来，就直接省去了最后一个步骤。
Talk is cheap , show me your code .
#include
using namespace std ;
const int N = 3010 ;
int a[N] , b[N] ;
int f[N][N] ;
int main()
{
int n ;
cin >> n ;
for(int i = 1 ; i <= n ; ++i)
cin >> a[i] ;
for(int j = 1 ; j <= n ; ++j)
cin >> b[j] ;
for(int i = 1 ; i <= n ; ++i)
{
int maxv = 1 ;
for(int j = 1 ; j <= n ; ++j )
{
f[i][j] = f[i-1][j] ;
if(a[i] == b[j])
{
f[i][j] = max(f[i][j] , maxv) ;
}
if(a[i] > b[j])
{
maxv = max(maxv , f[i-1][j] + 1) ;
}
}
}
int res = 0 ;
for(int i =1 ; i <= n ; ++ i)
{
res = max(res , f[n][i]) ;
}
cout << res << endl ;
return 0 ;
}
好吧，在懂了思路逻辑之后，进行修改就比较好理解了。
由于遍历顺序是由小到大，所以我们完全可以针对每一个i来优先定义一个maxv，主要是用于储存最大的倒数第二的值，(这样说好像有一点抽象)， 其实就是省略了一部再找最大值的步骤，他是从一个小循环的一开始，就定义了一个基底，用于找最大值，跟这循环一起走的，就完全不需要再开一个循环进行查找了。这样就可以将时间复杂度降低到2了。
题外话
其实在看y总的讲解之后，我是感觉有点被打破思考模式的感觉，就是感觉就算是做了前置的LIS与LCS，但是遇到这种题，思路还是没有明显。
甚至有很多问题：
一、为什么要以j定位？
二、如何体现有c有l？
总之，刷题的意义在于利用旧的知识，在遇到新的问题的时候，可以顺利的想到多种以前可以顺利解决的思路。所以，如果遇到一个问题，你感觉他不是你的框架里面的东西，但是看了答案之后，却发现你可以利用现有的知识完全的解决他们。这可以说明两个事情：
一、对以往的问题思考不够深入
二、知识框架过于片面与呆板
总之，学习能力的提升过程其实就是不断建立自己的思维模式的过程，不断建立，然后不断打破，然后再进行建立，这是正常过程。
继续坚持，随着时间与问题的堆积，你的思维模式会越来越多元化，框架会越来越硬，由flask变成django(hhhhh，玩个小梗) 。量变引起质变。
