题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1160
给你一些老鼠的体重和速度，问你最多需要几只可以证明体重越重速度越慢，并输出任意一组答案。
结构体按照体重从小到大排序，然后根据速度就是最长下降子序列。
1 //#pragma comment(linker, "/STACK:102400000, 102400000") 2 #include <algorithm> 3 #include <iostream> 4 #include <cstdlib> 5 #include <cstring> 6 #include <cstdio> 7 #include <vector> 8 #include <cmath> 9 #include <ctime> 10 #include <list> 11 #include <set> 12 #include <map> 13 using namespace std; 14 typedef long long LL; 15 typedef pair <int, int> P; 16 const int N = 1105; 17 struct Mouse { 18 int fat, run, id; 19 bool operator <(const Mouse& cmp) const { 20 if(fat == cmp.fat) 21 return run > cmp.run; 22 return fat < cmp.fat; 23 } 24 }a[N]; 25 int dp[N]; 26 int pre[N], ans[N]; 27 28 int main() 29 { 30 int f = 1; 31 while(scanf("%d %d", &a[f].fat, &a[f].run) != EOF) { 32 a[f].id = f; 33 f++; 34 } 35 for(int i = 0; i <= f; ++i) { 36 pre[i] = i; 37 } 38 sort(a + 1, a + f); 39 memset(dp, 0, sizeof(dp)); 40 int Max = 1, pos = 1; 41 for(int i = 1; i < f; ++i) { 42 dp[i] = 1; 43 for(int j = 1; j < i; ++j) { 44 if(a[i].fat > a[j].fat && a[i].run < a[j].run) { 45 if(dp[j] + 1 > dp[i]) { 46 pre[a[i].id] = a[j].id; 47 dp[i] = dp[j] + 1; 48 } 49 } 50 } 51 if(dp[i] > Max) { 52 pos = a[i].id; 53 Max = dp[i]; 54 } 55 } 56 printf("%d\n", Max); 57 int i = pos, cnt = 0; 58 for(i = pos; i != pre[i]; i = pre[i]) { 59 ans[++cnt] = i; 60 } 61 ans[++cnt] = i; 62 for(i = cnt; i >= 1; --i) { 63 printf("%d\n", ans[i]); 64 } 65 return 0; 66 }