最长非降子序列模型

桃扇骨 2022-08-26 14:27 226阅读 0赞

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

描述：

给定一整型数列\{a1,a2...,an\}（0<n<=100000），找出单调递增最长子序列，并求出其长度。

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

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

方法1：

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

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

**代码：**

#include<iostream>
    #include<string>
    #include<cstdio>
    #include<cstring>
    #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<len;i++)
            {
                max=0;
                for(j=i-1;j>=0;j--)
                {
                    if(s[i]>s[j]&&max<dp[j])
                    {
                        max=dp[j];
                    }
                }
                dp[i]=max+1;
                if(dp[i]>ans)
                    ans=dp[i];
            }
            printf("%d\n",ans);
        }
        return 0;
    }

方法2：

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

**详细分析：[http://blog.csdn.net/y990041769/article/details/8544081][http_blog.csdn.net_y990041769_article_details_8544081]**

**代码：**

#include <cstdio>
    #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]<ob)
                L=mid+1;
            else
                R=mid-1;
        }
        return L;
    }
    int main()
    {
        while(scanf("%d",&n)!=EOF)
        {
            for(int i=1;i<=n;i++)
            scanf("%d",a+i);
            len=0;
            int j;
            d[0]=-INF;
            for(int i=1;i<=n;i++)
            {
                if(a[i]>d[len])
                    j=++len;
                else
                    j=Find(1,len,a[i]);
                d[j]=a[i];
            }
            printf("%d\n",len);
        }
    
    }

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

**描述：**

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

**题目链接：[滑雪][Link 2]**

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

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

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

**代码：**

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    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<b.h;
    }
    int dp[N*N];
    int main()
    {
        int n,m;
        while(~scanf("%d%d",&n,&m))
        {
            int l=0;
            memset(a,0,sizeof(a));
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                {
                    scanf("%d",&map[i][j]);
                    a[l].x=i,a[l].y=j,a[l++].h=map[i][j];
                }
            }
            std::sort(a,a+l,comp);
            memset(dp,0,sizeof(dp));
            int max=1;dp[0]=1;
            for(int i=1;i<l;i++)
            {
                //printf("%d %d %d\n",a[i].h,a[i].x,a[i].y);
                int tmp=0;
                for(int j=i-1;j>=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;
    }

也可以记忆话搜索，比dp快点

#include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    using namespace std;
    const int N =120;
    
    int map[N][N];
    int dp[N][N];
    int dx[6]={1,-1,0,0};
    int dy[6]={0,0,1,-1};
    int m,n;
    void dfs(int x,int y,int ddx,int ddy)
    {
        if(dp[x][y]>(dp[ddx][ddy]+1))
            return;
        //printf("YES\n");
        dp[x][y]=dp[ddx][ddy]+1;
        for(int i=0;i<4;i++)
        {
            int disx=dx[i]+x,disy=dy[i]+y;
            if(disx>=1 && disy>=1 && disx<=n && disy<=m && map[x][y]<map[disx][disy])
            {
                dfs(disx,disy,x,y);
            }
        }
    }
    int main()
    {
        //freopen("Input(1).txt","r",stdin);
        //freopen("OUT.txt","w",stdout);
        int T;
        scanf("%d",&T);
        while(T--)
        {
            scanf("%d%d",&n,&m);
            for(int i=1;i<=n;i++)
                for(int j=1;j<=m;j++)
                    scanf("%d",&map[i][j]);
            memset(dp,0,sizeof(dp));
            dp[110][110]=-1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++){//printf("YES\n");
                    dfs(i,j,110,110);
                }
    
            }
    
            int ans=-1;
            for(int i=1;i<=n;i++)
            {
                for(int j=1;j<=m;j++)
                    ans=max(ans,dp[i][j]);
            }
            printf("%d\n",ans+1);
        }
        return 0;
    }

[Link 1]: http://acm.nyist.net/JudgeOnline/problem.php?pid=17
[http_blog.csdn.net_y990041769_article_details_8544081]: http://blog.csdn.net/y990041769/article/details/8544081
[Link 2]: http://poj.org/problem?id=1088