DP|【基础练习】【线性DP】codevs1408 最长公共子序列（上升）题解
这道题目捣鼓了一个小时了终于弄出来咯···怒吼三声：容易吗！文章被盗还是很严重，加版权信息转载请注明出处 [ametake版权所有]http://blog.csdn.net/ametake欢迎来看
题目描述 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[i][j]表示a的前i个和b的前j个中的最长公共子序列长度，转移方程为：
xi = yj 时 , f[i,j] = f[i-1,j-1] + 1
xi <> yj时 , f[i,j] = max { f[i,j-1] , f[i-1,j] }
【【但是由于本题要求的是最长公共上升子序列，上升这个要求让他必须参考末尾元素的值，因此这个方程是不对的】】
我们先放上最长公共上升子序列的方程，比较一下：
a[i]!=b[j]:F[i][j]=F[i-1][j]
a[i]==b[j]:F[i][j]=max(F[i-1][k])+1 1<=k<=j-1&&b[j]>b[k]
这是什么意思？这里f[i][j]的意思发生了改变，他指的是：a的前i个和b的前j个中以b[j]为结尾的最长公共子序列
【为什么要以b[j]结尾？如果不以b[j]结尾，那么我们求出的f[i-1][k]也不一定是k结尾，所谓f[i][j]只是表示“a的前i个和b的前j个中的最长公共子序列长度”
这样就无法保证我们选择的b[k]
那么方程又进行了怎样的改变呢？对于方程的解释，请允许我引用@我们都爱刘汝佳的见解，原文地址在补充第三条
“首先，在a[i]!=b[j]的时候有F[i][j]=F[i-1][j]。为什么呢？因为F[i][j]是以b[j]为结尾的LCIS，如果F[i][j]>0那么就说明a[1]..a[i]中必然有一个字符a[k]等于b[j]（如果F[i][j]等于0呢？那赋值与否都没有什么影响了）。
因为a[k]!=a[i]，那么a[i]对F[i][j]没有贡献，于是我们不考虑它照样能得出F[i][j]的最优值。所以在a[i]!=b[j]的情况下必然有F[i][j]=F[i-1][j]。这一点参考LCS的处理方法。
那如果a[i]==b[j]呢？首先，这个等于起码保证了长度为1的LCIS。然后我们还需要去找一个最长的且能让b[j]接在其末尾的LCIS。之前最长的LCIS在哪呢？首先我们要去找的F数组的第一维必然是i-1。因为i已经拿去和b[j]配对去了，不能用了。并且也不能是i-2，因为i-1必然比i-2更优。第二维呢？那就需要枚举b[1]..b[j-1]了，因为你不知道这里面哪个最长且哪个小于b[j]。
这里还有一个问题，可不可能不配对呢？也就是在a[i]==b[j]的情况下，需不需要考虑F[i][j]=F[i-1][j]的决策呢？答案是不需要。因为如果b[j]不和a[i]配对，那就是和之前的a[1]..a[j-1]配对（假设F[i-1][j]>0，等于0不考虑），这样必然没有和a[i]配对优越。（为什么必然呢？因为b[j]和a[i]配对之后的转移是max(F[i-1][k])+1，而和之前的i`配对则是max(F[i`-1][k])+1。显然有F[i][j]>F[i`][j],i`>i） 于是我们得出了状态转移方程：
a[i]!=b[j]:F[i][j]=F[i-1][j]
a[i]==b[j]:F[i][j]=max(F[i-1][k])+1 1<=k<=j-1&&b[j]>b[k]”
因此核心代码为：
for (int i=1;
i<=n;
i++)
{
for (int j=1;
j<=n;
j++)
{
if (a[i]==b[j])
{
f[i][j]=1;
//remember or if there's not miner before it will be 0见下方说明
for (int k=j-1;
k>=1;
k--)//反向查找更快
{
if (b[k]
最后，只要在所有的f[n][j]中选择最大的就可以，因为f[n][j]一定是以b[j]结尾的公共上升子序列中最大的
那么放上O（n3）朴素版本代码
//codevs1408 最长公共子序列（上升） 线性DP
//copyright by ametake
//independently!cheer up!
#include
#include
#include
#include
using namespace std;
const int maxn=3000+10;
int f[maxn][maxn],a[maxn],b[maxn];
int n,l1,l2;
int main()
{
freopen("1.txt","r",stdin);
scanf("%d",&n);
for (int i=1;
i<=n;
i++) scanf("%d",&a[i]);
for (int i=1;
i<=n;
i++) scanf("%d",&b[i]);
memset(f,0,sizeof(f));
for (int i=1;
i<=n;
i++)
{
for (int j=1;
j<=n;
j++)
{
if (a[i]==b[j])
{
f[i][j]=1;
//remember or if there's not miner before it will be 0
for (int k=j-1;
k>=1;
k--)
{
if (b[k]
【DP|【基础练习】【线性DP】codevs1408 最长公共子序列（上升）题解】
接下来是平方级的代码，详情见下面补充：
//codevs1408 ×?3¤1?12×óDòáD￡¨é?éy￡? ??D?DP shijianfuzadu O(n2)ó??ˉ°?
//copyright by ametake
//independently!cheer up!
#include
#include
#include
#include
using namespace std;
const int maxn=3000+10;
int f[maxn][maxn],a[maxn],b[maxn];
int n,l1,l2;
int main()
{
freopen("1.txt","r",stdin);
scanf("%d",&n);
for (int i=1;
i<=n;
i++) scanf("%d",&a[i]);
for (int i=1;
i<=n;
i++) scanf("%d",&b[i]);
memset(f,0,sizeof(f));
for (int i=1;
i<=n;
i++)
{
int max=0;
for (int j=1;
j<=n;
j++)
{
f[i][j]=f[i-1][j];
if (a[i]>b[j]&&max
至于空间压缩为一位的算法，详情还是看链接吧，我在这里只放出核心代码：
for(i=1;
i<=n1;
i++)
{
max=0;
for(j=1;
j<=n2;
j++)
{
if (a[i]>b[j]&&max
最后请让我补充几个坑点：
1.输入数据是数字而不是字符串，每个数之间都有空格，按字符串读入会挂掉，因为字符串把空格当成结尾= =
2.如果i=j，变量k循环前，要先把f[i][j]赋值为1，否则如果找不到比当前j小的k的话，f[i][j]是0，会导致wa
3.本题O（n3）算法可以胜任，但还有平方算法和一维空间算法 详情参见http://wenku.baidu.com/view/3e78f223aaea998fcc220ea0.html上文中的解释也引自这篇文章 再次感谢@我们都爱刘汝佳 同时感谢多多帮助的里奥君~
——亦余心之所善兮，虽九死其犹未悔
推荐阅读
- 宽容谁
- 我要做大厨
- 增长黑客的海盗法则
- 画画吗（）
- 2019-02-13——今天谈梦想（）
- 远去的风筝
- 三十年后的广场舞大爷
- 叙述作文
- 20190302|20190302 复盘翻盘
- 学无止境，人生还很长