题目链接
题意：有好多行，每行两个数字，代表大象的体重和智商，求大象体重越来越大，智商越来越低的最长序列，并输出。
思路：先排一下序，再按照最长上升子序列计算就行。
还有注意输入，
刚开始我是这样输入的 cnt = 1;
while(~scanf("%d%d", &p[cnt].w, &p[cnt++].s))
结果p[1].w的值没有，为0， 所以注意在连续输入的时候不能用 cnt++;
1 #include <iostream> 2 #include <cstring> 3 #include <cstdio> 4 #include <algorithm> 5 using namespace std; 6 const int maxn = 10000+10; 7 struct node 8 { 9 int w, s, f; 10 }p[maxn]; 11 int d[maxn], h[maxn]; 12 13 bool cmp(node a, node b) 14 { 15 if(a.w == b.w) 16 return a.s > b.s; 17 else 18 return a.w < b.w; 19 } 20 void prin(int x) 21 { 22 if(h[x] == x) 23 { 24 printf("%d ", x); 25 return; 26 } 27 else 28 { 29 prin(h[x]); 30 printf("%d ", x); 31 } 32 } 33 int main() 34 { 35 int i, j, cnt = 1, tmp, x, ans; 36 while(~scanf("%d%d", &p[cnt].w, &p[cnt].s)) 37 { 38 p[cnt].f = cnt; 39 cnt ++; 40 } 41 sort(p+1, p+cnt, cmp); 42 d[1] = 1; h[p[1].f] = p[1].f; 43 for(i = 2; i < cnt; i++) 44 { 45 tmp = 1; x = p[i].f; 46 for(j = 1; j < i; j++) 47 { 48 if(p[i].w > p[j].w && p[i].s < p[j].s) 49 { 50 if(d[j] >= tmp) 51 { 52 tmp = d[j] + 1; 53 x = p[j].f; 54 } 55 } 56 } 57 d[i] = tmp; 58 h[p[i].f] = x; 59 } 60 ans = 0; 61 for(i = 1; i < cnt; i++) 62 if(d[i] > ans) 63 { 64 ans = d[i]; 65 x = p[i].f; 66 } 67 cout<<ans<<endl; 68 prin(x); 69 return 0; 70 }