FatMouse's Speed

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

用类似求最长不减子序列的方法，比较水，转移方程为:f[n] = max(f[n], f[i] + 1)-----满足w[n] > w[i] && s[n] < s[i];

刚开始WA了几次，因为没注意到是严格单调增的

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
struct node {
	int w;
	int s;
	int num;
}data[1010];
int pre[1010];
int len[1010];
bool cmp(const node& A, const node& B) {
	if(A.w != B.w) return A.w < B.w;
	return A.s > B.s;
}
void print(int index) {
	if(len[index] == 1) {
		cout << data[index].num << endl;
		return;
	}
	print(pre[index]);
	cout << data[index].num << endl;
}
int main() {
	//freopen("1.txt", "r", stdin);
	int n = 0;
	while(cin >> data[n].w >> data[n].s) {
		data[n].num = n + 1;
		n++;
	}
	sort(data, data + n, cmp);
	memset(pre, 0, sizeof(pre));
	for(int i = 0; i < n; i++) len[i] = 1;
	for(int i = 1; i < n; i++) {
		for(int j = 0; j < i; j++) {
			if(data[j].w != data[i].w && data[j].s > data[i].s) {
				int tmpLen = len[j] + 1;
				if(tmpLen > len[i]) {
					len[i] = tmpLen;
					pre[i] = j;
				}
			}
		}
	}
	int index = 0;
	for(int i = 1; i < n; i++)
		if(len[i] > len[index]) index = i;
	cout << len[index] << endl;
	print(index);
	return 0;
}