题解 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]枚举一遍，找到最大值（即是不下降子序列的最长长度）输出即可，此题得解 ```cpp #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; } ```