思路：
f[i][j]表示n1串第i个与n2串第j个且以j结尾的LCIS长度。
很好想的一个DP。
然后难点是优化。这道题也算是用到了DP优化的一个经典类型吧。
可以这样说，这类DP优化的起因是发现重复计算了很多状态，比如本题k的那层循环。
然后就可以用maxl标记搞一下，将O(n^3)变成O(n^2).
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
#define INF 0x3f3f3f3f
#define MAXN 3100
int n1[MAXN],n2[MAXN];
int n;
int f[MAXN][MAXN];
int ff[MAXN]; inline void deal(int &x,int y)
{
x=max(x,y);
}
int main()
{
//freopen("input.txt","r",stdin);
//freopen("output.txt","w",stdout);
int i,j;
scanf("%d",&n);
for (i=;i<=n;i++)
{
scanf("%d",&n1[i]);
}
for (i=;i<=n;i++)
{
scanf("%d",&n2[i]);
}
memset(f,,sizeof(f));
memset(ff,-INF,sizeof(ff));
f[][]=;
int maxl=;
for (i=;i<=n;i++)
{
maxl=;
for (j=;j<=n;j++)
{
if (n1[i]>n2[j])deal(maxl,f[i-][j]);
if (n1[i]==n2[j])
{
deal(f[i][j],maxl+);
/* for (k=j-1;k>=0;k--)
{
if (n2[k]<n2[j])deal(f[i][k],f[i-1][k]);
}*/
}else
{
deal(f[i][j],f[i-][j]); }
}
}
int ans=;
for (i=;i<=n;i++)
{
deal(ans,f[n][i]);
}
cout<<ans<<endl;
}