题目链接
题意：有好多行，每行两个数字，代表大象的体重和智商，求大象体重越来越大，智商越来越低的最长序列，并输出。
思路：先排一下序，再按照最长上升子序列计算就行。
还有注意输入，
刚开始我是这样输入的 cnt = 1;
while(~scanf("%d%d", &p[cnt].w, &p[cnt++].s))
结果p[1].w的值没有，为0， 所以注意在连续输入的时候不能用 cnt++;
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = +;
struct node
{
int w, s, f;
}p[maxn];
int d[maxn], h[maxn]; bool cmp(node a, node b)
{
if(a.w == b.w)
return a.s > b.s;
else
return a.w < b.w;
}
void prin(int x)
{
if(h[x] == x)
{
printf("%d\n", x);
return;
}
else
{
prin(h[x]);
printf("%d\n", x);
}
}
int main()
{
int i, j, cnt = , tmp, x, ans;
while(~scanf("%d%d", &p[cnt].w, &p[cnt].s))
{
p[cnt].f = cnt;
cnt ++;
}
sort(p+, p+cnt, cmp);
d[] = ; h[p[].f] = p[].f;
for(i = ; i < cnt; i++)
{
tmp = ; x = p[i].f;
for(j = ; j < i; j++)
{
if(p[i].w > p[j].w && p[i].s < p[j].s)
{
if(d[j] >= tmp)
{
tmp = d[j] + ;
x = p[j].f;
}
}
}
d[i] = tmp;
h[p[i].f] = x;
}
ans = ;
for(i = ; i < cnt; i++)
if(d[i] > ans)
{
ans = d[i];
x = p[i].f;
}
cout<<ans<<endl;
prin(x);
return ;
}