首页 > 代码库 > zoj2319Beautiful People Dp
zoj2319Beautiful People Dp
最长上升子序列的nlogn的解法,不过要注意的是 x按从小到大排序,y要按从大到小排序。对于同样的x,在维护的单调数组中y应该保留较小的那个。
#include<iostream>#include<iostream>#include<cstdio>#include<cstring>#include<map>#include<vector>#include<stdlib.h>#include<algorithm>using namespace std;const int maxn = 111111;typedef long long LL;struct Node{ int x; int y; int id;}node1[maxn],node[maxn];int erfen(int a[], int l, int r, int key){ int ans = -1; while (l <= r){ int mid = (l + r) >> 1; if (a[mid] > key) { ans = mid; } if (a[mid] > key) r = mid - 1; else l = mid + 1; } return ans;}int cmp(const Node &a,const Node &b){ if(a.x==b.x) return a.y>b.y; return a.x<b.x;}int ans[maxn];int cnt;int vis[maxn];int father[maxn];void showpath(int x){ while(x!=father[x]){ printf("%d ",x);x=father[x]; } printf("%d",x); cout<<endl;}int main(){ int T,n; cin >> T; while (T--){ cin >> n; for (int i = 1; i <= n; i++){ scanf("%d%d", &node[i].x, &node[i].y); node[i].id = i; node1[i] = node[i]; } sort(node + 1, node + 1 + n, cmp); cnt = 1; ans[cnt] = node[1].y; vis[cnt++] = node[1].id; father[node[1].id] = node[1].id; //cout<<endl; //for(int i = 1;i<=n;i++) // printf("%d %d\n",node[i].x,node[i].y); //cout<<endl; for (int i = 2; i <= n; i++){ int t = erfen(ans, 1, cnt - 1, node[i].y); //printf("%d %d %d\n",t,ans[cnt-1],node[i].y);system("pause"); if (t == -1 && node1[vis[cnt - 1]].x < node[i].x&&node1[vis[cnt-1]].y<node[i].y){ father[node[i].id] = vis[cnt-1]; ans[cnt] = node[i].y; vis[cnt++] = node[i].id;; } if (t != -1){ if(t!=1&&node[i].y<=ans[t-1]) continue; ans[t] = node[i].y; vis[t] = node[i].id; if(t==1) father[node[i].id] = node[i].id; else father[node[i].id] = vis[t-1]; } } printf("%d \n",cnt-1); showpath(vis[cnt-1]); } return 0;}
zoj2319Beautiful People Dp
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。