UVA - 10131 Is Bigger Smarter? 最长上升子序列

题目大意：给出一系列大象的体重和IQ的数据，要求找出最长的一串，符合 大象1的体重大于大象2，而IQ却小于大象2

解题思路：设置一个状态量，d[i]，表示以第i只大象为终点的符合条件的最大值，则如果符合大象i的体重大于大象j的体重，但IQ却反之且d[i]  < d[j] + 1,那么d[i]  = d[j] + 1

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn = 10000 + 5;
struct elephant {
	int w;
	int i;
	int m;
}e[maxn];
int path[maxn],dp[maxn];

bool cmp(elephant e1,elephant e2) {
	return e1.w < e2.w ;
}

int main() {
	int k = 1;
	while(scanf("%d%d",&e[k].w,&e[k].i) != EOF) {
		e[k].m = k;
		k++;	
	}
	k--;
	sort(e+1,e+k,cmp);

	for(int i = 1; i <= k; i++) {
		dp[i] = 1;
		path[i] = i;
	}

	int first,max = -1;	

	for(int i = 1; i <= k; i++)
		for(int j = 1; j < i ;j++) {
			if(e[i].w > e[j].w && e[i].i < e[j].i && dp[i] < dp[j]+1) {
					dp[i] = dp[j] + 1;
					path[i] = j;	
			}
			if(max < dp[i]) {
				max = dp[i];
				first = i;	
			}
		}

	printf("%d\n",max);
	int i = first ;
	int ans[maxn],count = 0;
	while(max--) {
		ans[count++] = e[i].m;	
		i = path[i];
	}
	for(int i = count-1; i >= 0; i--)
		printf("%d\n",ans[i]);
	return 0;
}