Codeforces："North-East"

题目链接：

题目大意：空间内有$n$个点，现取$x$和$y$严格递增的点组成最长序列，问可能取到哪些点，一定取到哪些点.

DP

这道题要求的是二维LIS，可以按$x$递增排序将其降为一维，当横坐标相等时，因为要求坐标严格递增，按$y$递减排序。

从后面往前搞，$maxy[len]$记录LIS长度为$len$的点的最大$y$，若以当前点为结尾的LIS长度为$len$，当前点的$y$小于$maxy[len+1]$则为可能取到的点。

代码如下：

1 #include 
     
       2 #include 
      
        3 #include 
       
         4 #include 
        
          5 #define N 100005 6 using namespace std; 7 struct node{ 8     int x,y,id; 9     friend bool operator<(node a,node b){10         if(a.x==b.x)return a.y>b.y;11         return a.x
         

v[N];17 set

A,B;18 void init(){19 freopen("input.txt","r",stdin);20 freopen("output.txt","w",stdout);21 }22 bool cmp(int x,int y){23 return val[x]>val[y];24 }25 void output(){26 printf("%d",A.size());27 for(set

::iterator it=A.begin();it!=A.end();++it)28 printf(" %d",*it);29 printf("\n");30 printf("%d",B.size());31 for(set

::iterator it=B.begin();it!=B.end();++it)32 printf(" %d",*it);33 printf("\n");34 }35 int main(void){36 init();37 scanf("%d",&n);38 for(int i=0;i

=0;--i){55 int id=a[i].id;56 int p=pos[id];57 if(val[id]