浅时光

用户名：YYB

访问量：2755

签　名：

等　　级
排　　名	627
经　　验	4113
参赛次数	5
文章发表	4
年　　龄	0
在职情况	学生
学　　校
专　　业

　　自我简介：

TA的其他文章

【密码】-题解(C++代码)
浏览：150

你可能喜欢

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

信息学奥赛一本通T1263-友好城市-题解(C++代码)

　　作者: 浅时光　　　　发表时间：2020-02-12 11:48:02 浏览：867　|　评论：0　

原题链接：信息学奥赛一本通T1263-友好城市

##### # 首先可以把一边河岸排一下序。于是样例就变成了这样：

| 南岸  | 北岸  |
| ------------ | ------------ |
|  2 |  6 |
|  4 | 2  |
|  9 |  8 |
|  10 |  3 |
|  15 | 12  |
|  17 | 17  |
|  22 | 4  |

###### 由于南岸已经排好序，如果北岸批准的申请城市不是一个递增序列的话，一边递增，一边递减，就会交叉。所以问题就变成一个找北岸的最长不下降子序列。

#include<iostream>
    #include<cstdio>
    #include<algorithm>
    using namespace std;
    
    struct num{
        int a;
        int b;
    };
    
    
    bool compare(const num &x,const num &y)
    {
        if (x.a>y.a) return false;
        else return true;
    }
    
    
    int main()
    {
        int n;
        num s[5001];
        cin>>n;
        for (int i=1;i<=n;++i)
        {
            cin>>s[i].a>>s[i].b;
        }
        sort(s+1,s+n+1,compare);
        const int hhh=n;
        int f[5001]={0};
        for (int i=n;i>=1;i--)
        {
            int t=0;    
            for (int j=i;j<=n;j++)
            {
                if (s[i].b<s[j].b&&f[j]>t)
                    t=f[j];
            }
            if (t==0) f[i]=1;
            else {
                f[i]=t+1;
            }
    
        }
        int max=0;
        for (int i=1;i<=n;i++)if (f[i]>max) max=f[i];
        cout<<max;
    }

0.0分

71 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

浅时光

TA的其他文章

你可能喜欢

汽水瓶（C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Hello, world! （C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

第一

信息学奥赛一本通T1263-友好城市-题解(C++代码)

评论区

精彩推荐

回文数字（C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

剔除相关数（C语言代码）

分糖果（C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

简单的a+b （C语言代码）

循环入门练习6 （C语言代码）

C二级辅导-进制转换（C语言代码）

淘淘的名单（C语言代码）

筛排处理（C语言代码）

浅时光

TA的其他文章

你可能喜欢

汽水瓶 （C语言代码）

2004年秋浙江省计算机等级考试二级C 编程题(1) （C语言代码）

Hello, world! （C语言代码）

汽水瓶 （C++代码）（直接n/2就可以了）

第一

信息学奥赛一本通T1263-友好城市-题解(C++代码)

评论区

精彩推荐

回文数字 （C++代码）

2004年秋浙江省计算机等级考试二级C 编程题(2) （C语言代码）

剔除相关数 （C语言代码）

分糖果 （C++代码）

C语言程序设计教程（第三版）课后习题6.2 （C语言代码）

简单的a+b （C语言代码）

循环入门练习6 （C语言代码）

C二级辅导-进制转换 （C语言代码）

淘淘的名单 （C语言代码）

筛排处理 （C语言代码）

汽水瓶（C语言代码）

汽水瓶（C++代码）（直接n/2就可以了）

　　评论区

回文数字（C++代码）

剔除相关数（C语言代码）

分糖果（C++代码）

C二级辅导-进制转换（C语言代码）

淘淘的名单（C语言代码）

筛排处理（C语言代码）