*想歪 [Acwing] 1012. 友好城市

https://www.acwing.com/problem/content/1014/

错误思路

不交叉 那么肯定是求最大上升子序列

因为左边能对应右边 所以需要求4遍LIS(左右从头开始的LIS 左右从尾开始的LIS) 然后取max

结果WA了 (还没搞清楚)

正解

我们需要把一个岸的 城市 排个序 之后呢 再对其 友好城市 求一遍LIS

(排序这里nb)

code(正解)

#include 
using namespace std;
const int N = 5e3+10;
int f[N],n;
struct node
{
    int  a,b;
}num[N];
bool cmp(node x,node y)
{
    return x.a>n;
    for(int i=1;i>num[i].a>>num[i].b;
    sort(num+1,num+1+n,cmp);
    for(int i  =1;i