首页 > 代码库 > ural 1112，LIS
ural 1112，LIS
题目链接：http://acm.timus.ru/problem.aspx?space=1&num=1112
题意：n根线段，要拿走一些，使得任何的线段的左段没有在某一个线段的内部。
其实说白了，就是拿走最少的线段，使得不重合。
数据量很小，100，直接LIS O(n^2)搞。
首先按x从小到大排，然后，按x搞lis 跟前面的线段的y比，然后记录前驱就ok了。
然后输出，刚开始准备递归输出的，想了下，没出来，就暴力的又存了一遍，其实还是可以递归输出的，只要找最前的一个线段，这里的最前的线段不确定，就利用一个ans变量，看要递归多少层。
#include <bits/stdc++.h>using namespace std;#define maxn 105struct Line{ int x,y;} lines[maxn];bool cmp(Line a,Line b){ return a.x<b.x;}int dp[maxn];int prev[maxn];int ans = 0;void print (int pos){ if(ans!=1) { --ans; print(prev[pos]); } printf("%d %d\n",lines[pos].x,lines[pos].y);}int main(){ memset(dp,0,sizeof(dp)); int n; scanf("%d",&n); for(int i=0; i<n; i++) { int x,y; scanf("%d%d",&x,&y); if(x>y) swap(x,y); lines[i].x = x,lines[i].y = y; } sort(lines,lines+n,cmp); dp[0] = 1; for(int i=1; i<n; i++) { int k = 0; int pos = -1; for(int j = 0; j<i; j++) { if(lines[j].y<=lines[i].x&&k<dp[j]) { k = dp[j]; pos = j; } } dp[i] = k + 1; if(pos!=-1) prev[i] = pos; } ans = 0; int pos = -1; for(int i=0; i<n; i++) { if(ans<dp[i]) { ans = dp[i]; pos = i; } } printf("%d\n",ans); /* vector<Line> vaj; for(int i=0; i<ans; i++) { vaj.push_back(lines[pos]); //printf("%d %d\n",lines[pos].x,lines[pos].y); pos = prev[pos]; } for(int i = ans-1;i>=0;i--) printf("%d %d\n",vaj[i].x,vaj[i].y); */ print(pos); return 0;}
ural 1112，LIS
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。