首页 > 代码库 > 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