您当前的位置: 首页 > 

不牌不改

暂无认证

  • 0浏览

    0关注

    422博文

    0收益

  • 0浏览

    0点赞

    0打赏

    0留言

私信
关注
热门博文

P2782 友好城市

不牌不改 发布时间:2022-03-11 19:42:39 ,浏览量:0

题目

题目链接

题解

最长上升子序列。

存在加强数据,动态规划的最长上升子序列只能过基础数据, O ( n 2 ) O(n^2) O(n2)。加强数据需要使用贪心优化的 O ( n l o g n ) O(nlogn) O(nlogn)做法。

难点有二:

  1. 想到先排序;
  2. 想到用最长上升子序列.

这种题想到先排序应该是要靠题量累积起来的,一开始我是直接按照输入顺序(即无序)进行遍历,要求只要第i个桥的两端城市坐标比第j个桥两端的城市坐标都大,那么就可以由第j个城市转移而来。

但是样例就错了,所以想到了先对一端的城市排序,先保证一端的城市是递增的,再对另一端进行上升子序列操作,这样就保证了另一端也是递增的了。

有关优化的代码及讲解。

导弹拦截题目的讲解,里面也讲解了优化的思考过程

代码 未优化
#include
#define PII pair 
#define x first
#define y second
using namespace std;

const int N = 1e5+10;

int n, f[N], a, b, ans;
vector  v;

int main()
{
	cin >> n;
	for (int i = 1;i > a >> b,
		v.push_back ({a, b});

	sort (v.begin (), v.end ());
	
	for (int i = 0;i  a >> b,
		v.push_back ({a, b});

	sort (v.begin (), v.end ());
	
	for (int i = 0;i  d[len]) d[++len] = j;
		else d[binary_search (j)] = j;
	}
	
	cout             
关注
打赏
1662186765
查看更多评论
0.1101s