最长非降子序列模型（poj1088）

1)首先最长单调非增子序列(一维)

描述：

给定一整型数列{a₁,a₂...,a_n}（0

如：1 9 10 5 11 2 13的最长单调递增子序列是1 9 10 11 13，长度为5。

题目链接：http://acm.nyist.net/JudgeOnline/problem.php pid=17点击打开链接

方法1：

运用转移方程 dp【i】=max（dp【j】）+1 ( j < i 且a [ i ] > a[ j ])

意思就是当前选择是在前面满足条件的基础上最大的值，然后+1

代码：

#include
  
   
#include
   
     #include
    
      #include
     
       #define N 10010 using namespace std; int dp[N]; char s[N]; int main() { int len,test,i,j,max; scanf("%d",&test); while(test--) { scanf("%s",&s); len=strlen(s); dp[0]=1; int ans=1; for(i=1;i
      
       =0;j--) { if(s[i]>s[j]&&max
       
        ans) ans=dp[i]; } printf("%d\n",ans); } return 0; }
       
      
     
    
   
  

运用二分查找，如果后一个值比已有的递增序列的最后一个大，那么可以放在后面使得序列长度+1，否则二分查找找出位置，把比它大的值更新小，这样下次插入的时候能够插入更多的值，时间复杂度较低!

详细分析：http://blog.csdn.net/y990041769/article/details/8544081

代码：

 
#include 
  
   
#define INF 0x7fffffff
int n;
int a[100005];
int d[100005];
int len;
int Find(int L,int R,int ob)
{
    while(L<=R)
    {
        int mid=(L+R)/2;
        if(d[mid]==ob)
            return mid;
        else if(d[mid]
   
    d[len]) j=++len; else j=Find(1,len,a[i]); d[j]=a[i]; } printf("%d\n",len); } } 
   
  

2）二维求一个最长递增序列

描述：

从任意一点开始，每次可以选择四周相邻的点且比他值小的走，每个点只能走一次，求走出来的一个最长的序列。

题目链接：滑雪

分析：按照最长单调递增子序列的思想

首先把它的图转化存入一个结构体中，存入行，列，以及值，按值的大小从小到大排序，同样运用前面的转移方程运用转移方程 dp【i】=max（dp【j】）+1 ( j < i 且a [ i ] > a[ j ])

注意点：每次只能走相邻的点。所以一定判断好，在这边wa了、

代码：

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       const int N =120; struct Node { int x,y; int h; }; Node a[N*N]; int map[N][N]; int comp(Node a,Node b) { if(a.h!=b.h) return a.h
      
       =0;j--) { if(abs(a[i].x-a[j].x)==1 && abs(a[i].y-a[j].y)==0 && a[i].h>a[j].h && dp[j]>tmp ) //没有搞清楚关系 tmp=dp[j]; if(abs(a[i].y-a[j].y)==1 && abs(a[i].x-a[j].x)==0 && a[i].h>a[j].h && dp[j]>tmp) tmp=dp[j]; } dp[i]=tmp+1; //printf("%d ",dp[i]); if(dp[i]>max) max=dp[i]; } printf("%d\n",max); } return 0; }