首页 > 代码库 > Gym 101246H ``North-East''（LIS）
Gym 101246H ``North-East''（LIS）
http://codeforces.com/gym/101246/problem/H
题意：
给出n个点的坐标，现在有一个乐队，他可以从任一点出发，但是只能往右上方走（包括右方和上方），要经过尽量多的点。输出它可能经过的点和一定会经过的点。
思路：
分析一下第一个案例，在坐标图上画出来，可以发现，他最多可以经过4个点，有两种方法可以走。
观察一下，就可以发现这道题目就是要我们求一个LIS。
首先，对输入数据排一下顺序，x小的排前，相等时则将y大的优先排前面。
用二分法求LIS，这样在d数组中就可以保存以第i个数结尾的LIS。
求完之后，我们从后往前分析，如果当前点处于第x个位置（也就是LIS的第x个数），如果第x+1个位置的可走点的最大y值大于了当前点的y值，那么当前点是可以选的。在此过程中，动态维护LIS每个位置可走点的最大y值。当然了，还要记录每个位置可走点的个数（这个为第二个答案做铺垫，因为当一个点是可选的并且它所在的LIS位置上只有一个可走点，那么这个点肯定是要经过的）。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath>10 #include<map>11 using namespace std;12 typedef long long ll;13 typedef pair<int,int> pll;14 const int INF = 0x3f3f3f3f;15 const int maxn=1e5+5;16 17 int n;18 19 struct Point20 {21 int x, y;22 int id;23 bool operator < (const Point& rhs) const24 {25 return x<rhs.x || (x==rhs.x && y>rhs.y);26 }27 }p[maxn];28 29 int g[maxn];30 int d[maxn];31 int h[maxn];32 33 int may[maxn];34 int cnt[maxn];35 36 vector<int> ans1, ans2;37 38 int main()39 {40 freopen("input.txt","r",stdin);41 freopen("output.txt","w",stdout);42 //freopen("in.txt","r",stdin);43 while(~scanf("%d",&n))44 {45 for(int i=1;i<=n;i++)46 {47 scanf("%d%d",&p[i].x, &p[i].y);48 p[i].id = i;49 }50 51 sort(p+1,p+n+1);52 int len = 0;53 for(int i=1;i<=n;i++) g[i]=INF;54 for(int i=1;i<=n;i++)55 {56 int k=lower_bound(g+1,g+n+1,p[i].y)-g;57 if(k==len+1) len++;58 d[i]=k;59 g[k]=p[i].y;60 }61 62 for(int i=1;i<=len;i++) h[i]=-INF;63 memset(may,0,sizeof(may));64 memset(cnt,0,sizeof(cnt));65 66 67 for(int i=n;i>=1;i--)68 {69 int x=d[i];70 if(x==len) {h[x]=max(h[x], p[i].y); may[i]=1; cnt[x]++;}71 else72 {73 if(h[x+1]>p[i].y) {h[x]=max(h[x],p[i].y); may[i]=1; cnt[x]++;}74 }75 }76 77 ans1.clear(); ans2.clear();78 79 for(int i=1;i<=n;i++)80 if(may[i]) ans1.push_back(p[i].id);81 sort(ans1.begin(),ans1.end());82 printf("%d ",ans1.size());83 for(int i=0;i<ans1.size();i++)84 {85 printf("%d%c",ans1[i],i==ans1.size()-1?‘\n‘:‘ ‘);86 }87 88 for(int i=1;i<=n;i++)89 if(may[i] && cnt[d[i]]==1) ans2.push_back(p[i].id);90 sort(ans2.begin(),ans2.end());91 printf("%d ",ans2.size());92 for(int i=0;i<ans2.size();i++)93 {94 printf("%d%c",ans2[i],i==ans2.size()-1?‘\n‘:‘ ‘);95 }96 }97 return 0;98 }
Gym 101246H ``North-East''（LIS）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。