题解 P1826 【猴子选大王数据再加强版】

哎呦不错呦 · 2018-10-22 20:05:13 · 题解

#include<bits/stdc++.h>
using namespace std;
struct citysail
{
    int start;//一端
    int end;//另一端
    int longest;//最长不下降子序列
}a[5200]={};//结构体存储请求的数据
bool mycmp(citysail a,citysail b)
{
    return a.start<b.start;
}//对结构体排序的函数
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
    scanf("%d%d",&a[i].start,&a[i].end);//读入相关数据
    sort(a+1,a+1+n,mycmp);//根据一端点排序
    for(int i=1;i<=n;i++)
    a[i].longest=1;//每个点的最长不下降子序列长度默认为1
    int l=0;
    for(int i=n-1;i>=1;i--)
    {
        l=0;
        for(int j=i+1;j<=n;j++)
        if((a[j].longest>l)&&(a[i].end<a[j].end))
        l=a[j].longest;//如果ij之间的关系是不下降的子序列，而且j点的存储的不下降子序列长度比i大，那就用j点的数据更新i点的数据
        a[i].longest=l+1;//由于把i也接入了j的不下降子序列后面，所以要加1
    }
    int ans=-100;
    for(int i=1;i<=n;i++)
    ans=max(ans,a[i].longest);
    cout<<ans;//找出最大值。
    return 0;
}