uva 10131(最長遞增子序列)

題意：給出了一群大象的體重和IQ兩個參數值的序列，要求輸出最長的體重遞增，IQ遞減的子序列的長度，和這個子序列的每個元素的初始位置。

題解：最長遞增/遞減子序列模闆題，隻不過需要把這個子序列儲存下來。

#include <stdio.h>
#include <string.h>
#include <algorithm>
using namespace std;
const int N = 1005;
struct Ele {
	int weight;
	int iq;
	int num;
}s[N];
int n, m, f[N], res[N];

int cmp(Ele a, Ele b) {
	if (a.weight != b.weight)
		return a.weight < b.weight;
	else
		return a.iq > b.iq;
}

int lis() {
	int *temp = new int[n];
	int i, j, k, maxx;
	for (i = 0; i < n; i++)
		f[i] = i;
	for (i = 1, maxx = 1, k = 0; i < n; i++) {
		temp[i] = 1;
		for (j = 0; j < i; j++) {
			if (s[i].weight != s[j].weight && s[i].iq < s[j].iq && temp[j] + 1 > temp[i]) {//要求重量遞增，不能把重量相同的存起來
				temp[i] = temp[j] + 1;
				f[i] = j;
				if (maxx < temp[i]) {
					maxx = temp[i];
					k = i;
				}
			}
		}
	}
	i = maxx - 1;
	while (f[k] != k) {
		res[i--] = s[k].num;
		k = f[k];
	}
	res[i] = s[k].num;
	return maxx;
}

int main() {
	while (scanf("%d%d", &s[n].weight, &s[n].iq) != EOF) {
		s[n].num = n;
		n++;
	}
	sort(s, s + n, cmp);//先按體重從小到大排序
	int ans = lis();
	printf("%d\n", ans);
	for (int i = 0; i < ans; i++)
		printf("%d\n", res[i] + 1);
	return 0;
}