做网站源码要给客户嘛,wordpress获取文章发布时间,怎么查看网站有没有做ssl,个人网站的制作模板Palmia国有一条横贯东西的大河#xff0c;河有笔直的南北两岸#xff0c;岸上各有位置各不相同的N个城市。 北岸的每个城市有且仅有一个友好城市在南岸#xff0c;而且不同城市的友好城市不相同。 每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市#xff0c;但…Palmia国有一条横贯东西的大河河有笔直的南北两岸岸上各有位置各不相同的N个城市。 北岸的每个城市有且仅有一个友好城市在南岸而且不同城市的友好城市不相同。 每对友好城市都向政府申请在河上开辟一条直线航道连接两个城市但是由于河上雾太大政府决定避免任意两条航道交叉以避免事故。 编程帮助政府做出一些批准和拒绝申请的决定使得在保证任意两条航线不相交的情况下被批准的申请尽量多。
输入 第 1 行一个整数 N表示城市数。 第 2 行到第 n1 行每行两个整数中间用1个空格隔开分别表示南岸和北岸的一对友好城市的坐标。
输出格式 仅一行输出一个整数表示政府所能批准的最多申请数。
数据范围 1 ≤ N ≤ 5000, 0 ≤ xi ≤ 10000
Input 7 22 4 2 6 10 3 15 12 9 8 17 17 4 2
Output 4
解析 假如将一边从小到大排序之后另一边的合法建桥的编号也一定是严格递增的。否则如果不严格递增的话一定会出现一个城市两条桥或者两条桥相交的情况这就不合法了。 所以这道题就转化为将一边从小到大排序另一边的最长上升子序列长度就是答案。
#include bits/stdc.h
#include math.h
using namespace std;
#define int long long
#define endl \n
#define ios ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
int gcd(int a,int b) { return b? gcd(b,a%b) : a; }
typedef pairint,int PII;
const double PIacos(-1.0);
const int N1e4;
int n;
struct node
{int l,r;
}str[N];
bool cmp(node a,node b)
{if (a.l!b.l) return a.lb.l;else return a.rb.r;
}
int f[N];
void solve()
{cinn;for (int i1;in;i) cinstr[i].lstr[i].r;sort (str1,strn1,cmp);for (int i1;in;i){f[i]1;for (int j1;ji;j){if (str[j].rstr[i].r) f[i]max(f[i],f[j]1);}}int ans0;for (int i1;in;i) ansmax(ans,f[i]);coutans;
}
signed main()
{ios;int T1;//cinT;while (T--) solve(); return 0;
}
