ZOJ 1076 Gene Assembly LIS

题目大意：

题目前面都是废话。

给你一串基因，然后给你上面的外显子的起始和终止位置，求最长上升子序列(LIS)

并且输出这些外显子的序号

思路：

直接DP，DP更新的时候用一个数组记录当前结点上一个是什么。最后用类似并查集的方法找到最开始的那一个。

#include
  
   
#include
   
     #include
    
      using namespace std; const int MAXN=50000+10; struct exons { int begin,end; int id; }a[MAXN]; bool operator < (const exons &x,const exons &y) { return x.begin < y.begin || x.begin==y.begin && x.end < y.end; } int dp[MAXN]; int pre[MAXN]; int ans[MAXN]; int main() { int n; while(~scanf(%d,&n),n) { for(int i=0;i
     
      = a[j].end && dp[i] < dp[j]+1) { dp[i]=dp[j]+1; pre[i]=j; } } } int len=0; for(int i=n-1;i!=-1;i=pre[i]) { ans[len++]=a[i].id; } for(int i=len-1;i>0;i--) printf(%d ,ans[i]); printf(%d ,ans[0]); //printf(%d ,dp[n-1]); } return 0; }