友好城市
题目 友好城市
思路分析
初始给定我们 n座打算建造的桥
每座桥有两个参数 x1和 x2，表示该桥一头连接在上岸坐标为x1的地方，一头连在下岸坐标为x2 的地方
找出一种建桥方案，使得在所有建造的桥不相交的前提下，建造尽可能多的桥
红色虚线表示初始提供的打算建造的桥
我们要找出的方案是在不相交的前提下的最大建桥数量
也就是上面的绿线连接而成的方案
先想一下暴力怎么做
很容易想到，我们可以枚举所有的方案，然后检查方案是否合法，如果合法就考虑是否能够更新最大值答案
这么做的时间复杂度是 \(O(2^n)\)，而 n的数据范围是 5000，毫无疑问会超时。
所以，我们就需要找出一些性质进行优化
既然是要暴力枚举，我们可以考虑一个枚举方案，按照上岸的坐标从小到大来枚举
然后我们只需关心下岸的坐标之间有何关系即可
于是，可以轻易发现，上坐标从小到大枚举选择到的桥，其对应下坐标也必然是从小到大的
具体见下图：
蓝色表示该方案按照上坐标从小到大先选出来的桥
红色表示该方案的下一座桥的下坐标不是从小到大的，绿色表示是从小到大的
因此，该方案中，在上坐标排序的情况下，下坐标次序不是从小到大的，则必然不合法（会有相交）
于是，这题就变成了：桥以上坐标从小到大排序后，找出下坐标的最长上升子序列长度
妙……
用pair把桥的两头存下来 然后按第一维（上坐标）排序
然后只需要对排序后的下坐标求最长上升子序列就行了
由于这题是只需要一个最大长度 所以还可以用单调栈加二分进一步优化
代码实现
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=5010;
int f[N];
PII bridge[N];
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>bridge[i].x>>bridge[i].y;
sort(bridge+1,bridge+n+1);
for(int i=1;i<=n;i++){
f[i]=1;
for(int j=1;j<i;j++){
if(bridge[j].y<bridge[i].y)
f[i]=max(f[i],f[j]+1);
}
}
int res=0;
for(int i=1;i<=n;i++)
res=max(res,f[i]);
cout<<res;
return 0;
}
#include<bits/stdc++.h>
using namespace std;
#define x first
#define y second
typedef pair<int,int> PII;
const int N=5010;
PII bridge[N];
int stk[N],top;
int n;
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
cin>>bridge[i].x>>bridge[i].y;
sort(bridge+1,bridge+n+1);
for(int i=1;i<=n;i++){
if(top==0 || bridge[i].y>stk[top])
stk[++top]=bridge[i].y;
else{
*lower_bound(stk+1,stk+top+1,bridge[i].y)=bridge[i].y;
}
}
cout<<top;
return 0;
}
💬 评论