现在的位置: 首页 > 综合 > 正文

hdu1160最长子序列

2014年02月03日 ⁄ 综合 ⁄ 共 854字 ⁄ 字号 评论关闭
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<queue>
#include<algorithm>
#include<map>
#include<iomanip>
#define INF 99999999
using namespace std;

const int MAX=1001;
int sum[MAX][2],**s;//sum[i][]记录以第i个元素为最后元素的最长子序列的长度和该元素前一个元素 

bool cmp(int *a,int *b){
	if(a[0] == b[0])return a[1]>b[1];
	return a[0]<b[0];
}

void DFS_output(int i){
	if(sum[i][1] == i){
		cout<<s[i][2]+1<<endl;
		return;
	}
	DFS_output(sum[i][1]);
	cout<<s[i][2]+1<<endl;
}

int main(){
	int n=0,k;
	s=new int*[MAX];
	for(int i=0;i<MAX;++i)s[i]=new int[3];
	while(cin>>s[n][0]>>s[n][1]){s[n][2]=n;++n;}
	sort(s,s+n,cmp);
	for(int i=0;i<n;++i){
		k=i;
		for(int j=0;j<i;++j){
			if(s[i][1]<s[j][1] && s[i][0]>s[j][0] && sum[j][0]>sum[k][0])k=j;
		}
		sum[i][0]=sum[k][0]+1;
		sum[i][1]=k;
	}
	k=0;
	for(int i=1;i<n;++i)if(sum[i][0]>sum[k][0])k=i;
	cout<<sum[k][0]<<endl;
	DFS_output(k);
	return 0;
}

http://acm.hdu.edu.cn/showproblem.php?pid=1160

抱歉!评论已关闭.