首页 > 代码库 > Codeforces："North-East"

Codeforces："North-East"

2024-09-20 05:37:57   216人阅读

Codeforces："North-East"

题目链接：http://codeforces.com/gym/101246/problem/H

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

DP

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

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

代码如下：

 1 #include <cstdio> 2 #include <algorithm> 3 #include <vector> 4 #include <set> 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<b.x;12     }13 }a[N];14 const int inf=1000005;15 int n,dp[N],val[N],k,pos[N],maxy[N];16 vector<int>v[N];17 set<int>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<int>::iterator it=A.begin();it!=A.end();++it)28         printf(" %d",*it);29     printf("\n");30     printf("%d",B.size());31     for(set<int>::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<n;++i){39         scanf("%d%d",&a[i].x,&a[i].y);40         a[i].id=i+1;41     }42     sort(a,a+n);43     for(int i=0;i<n;++i){44         int v=a[i].y;45         int t=lower_bound(dp,dp+k,v)-dp;46         dp[t]=v;47         val[a[i].id]=a[i].y;48         pos[a[i].id]=t;49         if(t==k)k++;50     }51     for(int i=0;i<k;++i)52         maxy[i]=-inf;53     maxy[k]=inf;54     for(int i=n-1;i>=0;--i){55         int id=a[i].id;56         int p=pos[id];57         if(val[id]<maxy[p+1]){58             A.insert(id);59             maxy[p]=max(maxy[p],val[id]);60             v[p].push_back(id);61         }62     }63     for(int i=0;i<k;++i)64         if((int)v[i].size()==1)65             B.insert(v[i][0]);66     output();67 }

 

Codeforces："North-East"


联系
我们