fatmouse's speed(dp).cpp

杭电acm解题报告2001---2099.

#include <cstdio>
#include <string>
#include <cstdlib>
#include <vector>
#include <algorithm>
using namespace std;
#define NMAX 1100

struct node {
	int w,s;
	int num;
	bool operator < (const node & t) const {
		if (w != t.w) {
			return w < t.w;
		}
		return s > t.s;
	}
}mice[NMAX];
int n;
int dp[NMAX],pre[NMAX];

int main()
{
	int i,j,t;
	n = 0;
	while (scanf("%d %d", &mice[n].w, &mice[n].s)==2) {
		mice[n].num = n+1;
		n ++;
	}
	sort(mice,mice+n);
	dp[0] = 1;
	pre[0] = 0;
	for (i=1;i<n;i++) {
		dp[i] = 1;
		pre[i] = i;
		for (j=0;j<i;j++) {
			if (mice[i].w > mice[j].w && mice[i].s < mice[j].s && dp[j]+1 > dp[i]) {
				dp[i] = dp[j] +1;
				pre[i] = j;
			}
		}
	}//for i
	int max_pos = 0;
	for (i=1;i<n;i++) {
		if (dp[i] > dp[max_pos]) {
			max_pos = i;
		}
	}
	printf("%d\n", dp[max_pos]);
	vector<int> seq;
	seq.clear();
	while (pre[max_pos] != max_pos) {
		seq.push_back(mice[max_pos].num);
		max_pos = pre[max_pos];
	}
	seq.push_back(mice[max_pos].num);
	for (i=seq.size()-1; i>=0 ;i--) {
		printf("%d\n", seq[i]);
	}
}