本文主要是介绍ACdream 1216 （ASC训练1） Beautiful People（DP），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目地址：http://acdream.info/problem?pid=1216
这题一开始用的是线段树，后来发现查询的时候还需要DP处理，挺麻烦。。也就不了了之了。。后来想到，这题其实就是一个二维的最长上升子序列。。
要先排序，先按左边的数为第一关键字进行升序排序，再按右边的数为第二关键字进行降序排序。这样的话，第一关键字相同的的肯定不在一个同一个上升子序列中。然后只对第二关键字进行复杂度为O(n*logn)的DP，找出最长上升序列，然后处理前驱，并输出即可。
代码如下：
#include <iostream>
#include <cstdio>
#include <string>
#include <cstring>
#include <stdlib.h>
#include <math.h>
#include <ctype.h>
#include <queue>
#include <map>
#include <set>
#include <algorithm>using namespace std;
#define LL long long
struct node
{int x, y, num;
}fei[110000];
int cmp(node x, node y)
{if(x.x==y.x)return x.y>y.y;return x.x<y.x;
}
int a[110000], d[110000], pre[110000], len, b[110000];
int bin_seach(int x)
{int low=0, high=len, mid, ans;while(low<=high){mid=low+high>>1;if(a[mid]>=x){high=mid-1;ans=mid;}else{low=mid+1;}}return ans;
}
int main()
{int n, i, j, pos, cnt;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++){scanf("%d%d",&fei[i].x,&fei[i].y);fei[i].num=i+1;}sort(fei,fei+n,cmp);len=1;a[1]=fei[0].y;d[0]=-1;d[1]=0;memset(pre,-1,sizeof(pre));for(i=1;i<n;i++){if(fei[i].y>a[len]){a[++len]=fei[i].y;pre[i]=d[len-1];d[len]=i;}else{pos=bin_seach(fei[i].y);a[pos]=fei[i].y;pre[i]=d[pos-1];d[pos]=i;}}printf("%d\n",len);cnt=0;/*for(i=0;i<n;i++){printf("%d ",fei[i].num);}puts("");*/for(i=d[len];i!=-1;i=pre[i]){b[cnt++]=fei[i].num;//printf("%d\n",i);}for(i=0;i<cnt-1;i++)printf("%d ",b[i]);printf("%d\n",b[cnt-1]);}return 0;
}
这篇关于ACdream 1216 （ASC训练1） Beautiful People（DP）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
