题解 P2782 【友好城市】

· · 题解

这是一本通上的一个例题，对于刚学动态规划的me来说当然不是一道水题，其实还是有一定难度的

首先我在本子上画了图，在数轴上描啊描，感觉这不和活动选择（一道贪心例题）一样么，于是就对它的一岸排了序，按照贪心策略来写（将每一对城市看作数轴上的一个区间，统计没有交集的区间最大个数）然后经老师提醒——这道题不能用贪心做！！如果两座城市一个从1到10，一个从2到11，贪心来讲是只能通过一对的，但是按题意可以都通过

所以，，在仔细琢磨了下，如果将一边排了序，能通过的城市对数一定是另一边的最长不下降子序列的长度（自己模拟下就好了，这样任意一对友好城市的连线与其他一对不会相交）

于是，难点又落在了求最长不下降子序列的长度上

用结构体a[i].num存储以a[i].s为最后一点的不下降子序列的长度，于是枚举每一个点（将枚举到的点设为A），看该点是否能与前面的点构成不下降子序列，于是又挨个枚举在该点之前的每一个点（将枚举到的点设为B），最终我们要的是满足1.B的s小于A的s,2.B的num(序列长度)是最大的，于是将a[B].num+1存入a[i].num中，使得a[i].num能与之前的最长序列合并组成新的最长序列

最后，线性地将a[i]枚举一遍，找到最大值（即是不下降子序列的最长长度）输出即可，此题得解

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
struct hh{
    int s;
    int n;
    int num=1;
}a[5001];
int read()
{
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    int h=0;
    while(ch<='9'&&ch>='0') 
    {
        h=h*10+ch-48;
        ch=getchar();
    }
    return h;
}
int n;
int my(const hh&a,const hh&b)
{
    return a.n<b.n;
}
int main()
{
    n=read();
    for(int i=1;i<=n;i++)
    {
        a[i].s=read();
        a[i].n=read();
    }
    sort(a+1,a+n+1,my);//以南岸的顺序排序 
    for(int i=2;i<=n;i++)//数北岸的最长不下降序列 
    {
        int max1=0;
        for(int w=1;w<i;w++)
        {
            if(a[i].s>a[w].s&&a[w].num>max1)
            {
                max1=a[w].num;
            } 
        }
        a[i].num=max1+1;
    }
    int ans=0;
    for(int i=1;i<=n;i++) ans=ans>a[i].num?ans:a[i].num;
    cout<<ans;
    return 0;
}