本题目,我用了一种较简单的解题方法依然求LIS
但不同的是要先进行排序,排序方法为先按x 升序排序,在按照y降序排序,然后用nlogn算法即可求解LIS
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define INF 1000010000
const int maxn = 100100;
struct node {
int x,y,id;
node (int x=0,int y=0,int id=0):x(x),y(y),id(id){}
bool operator <(const node& rhs) const{
return x<rhs.x||x==rhs.x&&y>rhs.y;
}
}a[maxn]......
阅读全文