这道和zoj1025一样，本质是贪心算法，首先要求任意最长的序列，我们只要保证最长就行，也就是在一幅图中找一个最长的链，首先我们需要根据y排序（输入为x，y),因为y大的肯定在y小的后面，然后就直接贪心，前面取不到后面就不可能取到那个数，证明了贪心的正确性。
#include<cstdio> #include<algorithm> #include<cmath> #include<map> #include<iostream> #include<cstring> using namespace std; int n; struct node { int x,y,r; }a[1005]; bool cmp(node a,node b) { if(a.y<b.y) return 1; return 0; } int ans[1006]; int res; void dp(int xx) { ans[res++]=a[xx].r; for(int i=xx+1;i<n;i++) { if(a[i].x>a[xx].y) { dp(i); break; } } } int main() { // freopen("input.txt","r",stdin); while(scanf("%d",&n)==1&&n) { res=0; for(int i=0;i<n;i++) { scanf("%d%d",&a[i].x,&a[i].y); a[i].r=i+1; } sort(a,a+n,cmp); // for(int i=0;i<n;i++) // { // printf("%d %d ",a[i].x,a[i].y); // } dp(0); // printf("%d ",res); for(int i=0;i<res-1;i++) printf("%d ",ans[i]); printf("%d ",ans[res-1]); } }