题意：

求两个长度不超过3000的序列的最长公共上升子序列

思路： 

 

• 朴素解法：用f[i,j]表示a1~ai与b1~bj可以构成的以bj为结尾的LCIS的长度，三重循环求解：

for(res i=1 ; i<=n ; i++)    for(res j=1 ; j<=m ; j++)        if(a[i]==b[j])        {         　　for(res k=1 ; k

 

• 经过观察可以发现：当外层的i固定时，条件b[k]<a[i]也是固定的，所以当j增加1时，k的取值范围也只增加了1，即只有j可能进入新的决策集合，则可以优化为两重循环：

1 #include 
      
        2 #include 
       
         3 #include 
        
          4 using namespace std; 5  6 const int N=3010; 7 int a[N],b[N]; 8 int f[N][N]; 9 int n;10 11 int main()12 {13     scanf("%d",&n);14     for(int i=1 ; i<=n ; i++) scanf("%d",&a[i]);15     for(int i=1 ; i<=n ; i++) scanf("%d",&b[i]);16     17     for(int i=1 ; i<=n ; i++)18     {19         int val=0;//表示决策集合(即f[i-1][k]的最大值) 20         for(int j=1 ; j<=n ; j++)21         {22             if(a[i]==b[j]) f[i][j]=val+1;23             else f[i][j]=f[i-1][j];24             if(b[j]