最长上升子序列（LIS） dp典型例题（tzoj 矩形嵌套，Rectangles ）

5985: 矩形嵌套

题意：求最长递增子序列（包含两个元素）

思路：先找出关系式子；

li=lj+1（当ai<aj时）

两层循环 第一层i从1-n

第二层j 从0-i ；求出i前面的每个j 的max长度再加上自己即1 so要初始化dp【0-n】=1

#include<bits/stdc++.h>

using namespace std;

struct node{

    int x,y;

}qu[1005];

bool cmp(node a,node b)

{

    if(a.x==b.x)return a.y<b.y;

    return a.x<b.x;

}

int dp[1005];

int main()

{

    int t,n,i,j;

    cin>>t;

    while(t--){

        cin>>n;

        for(i=0;i<n;i++){

            int u,v;cin>>u>>v;

            qu[i].x=min(u,v);

            qu[i].y=max(u,v);

            dp[i]=1;

        }

        sort(qu,qu+n,cmp);

        for(i=1;i<n;i++){

            for(j=0;j<i;j++){

            //    cout<<i<<"  i-j "<<j<<" ";

                if(qu[j].x<qu[i].x&&qu[j].y<qu[i].y){

            //        cout<<dp[i]<<" "<<dp[j]+1;

                    dp[i]=max(dp[i],dp[j]+1);

                }

            //    cout<<endl;

            }

        }

        int maxx=dp[0];

        for(i=1;i<n;i++)maxx=max(maxx,dp[i]);

        cout<<maxx<<endl;

    }

    return 0;

}

3229: Rectangles

解法同上

#include<bits/stdc++.h>

using namespace std;

struct node{

    int x1,y1,x2,y2;

}qu[1005];

bool cmp(node a,node b)

{

    return a.x1<b.x1|| a.x1==b.x1&&a.y1<b.y1|| a.x1==b.x1&&a.y1==b.y1&&a.x2<b.x2|| a.x1==b.x1&&a.y1==b.y1&&a.x2==b.x2&&a.y2<b.y2;

}

int dp[1005];

int main()

{

    int t,n,i,j;

    while(scanf("%d",&n),n!=0){

        for(i=0;i<n;i++){

            scanf("%d%d%d%d",&qu[i].x1,&qu[i].y1,&qu[i].x2,&qu[i].y2);

            dp[i]=1;

        }

        sort(qu,qu+n,cmp);

        for(i=1;i<n;i++){

            for(j=0;j<i;j++){

                if(qu[j].x2<qu[i].x1&&qu[j].y2<qu[i].y1){

                    dp[i]=max(dp[i],dp[j]+1);

                }

            }

        }

        int maxx=dp[0];

        for(i=1;i<n;i++)maxx=max(maxx,dp[i]);

        printf("%d\n",maxx);

    }

    return 0;

}

这题也可以用记忆化搜索

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int N=1005;

struct p{

    int x1,x2,y1,y2;

}rec[N];

int vis[N][N],res[N],n;

int dfs(int u)

{

    if(res[u]) return res[u];

    for(int i=0;i<n;i++)

        if(vis[u][i]) res[u]=max(res[u],dfs(i)+1);

    res[u]=max(res[u],1);

    return res[u];

}

void init()

{

    memset(vis,0,sizeof(vis));

    memset(res,0,sizeof(res));

}

int main()

{

    while(~scanf("%d",&n),n)

    {

        init();

        for(int i=0;i<n;i++) scanf("%d%d%d%d",&rec[i].x1,&rec[i].y1,&rec[i].x2,&rec[i].y2);

        for(int i=0;i<n;i++)

            for(int j=0;j<n;j++)

                if(rec[i].x2<rec[j].x1&&rec[i].y2<rec[j].y1) vis[i][j]=1;

        int ans=0;

        for(int i=0;i<n;i++)

            ans=max(ans,dfs(i));

        printf("%d\n",ans);

    }

}

最长上升子序列（LIS） dp典型例题（tzoj 矩形嵌套，Rectangles ）的相关教程结束。