FatMouse's Speed --hdu

题目链接：https://vjudge.net/contest/226711#problem/E

题目大意：寻找最长上升序列（不分前后顺序，最长就行），输出最长的个数  以及 路径 下标

感悟：第一次输出dp路径， 刚开始想着用最短路径的路径输出方式类比一下，结果出现了问题， 弄错了排序前和排序后的下标（T_T）

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cmath>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long
using namespace std;
const int maxn=1050;
int path[maxn]= {0}, aim[maxn];
struct edge
{
    int x;
    int y;
    int id;
};
pair<int,int > dp[maxn];
edge e[maxn], pp[maxn];
bool cmp(edge x, edge y)
{
    if(x.x==y.x)
        return x.y>y.y;
    return x.x<y.x;
}
int main()
{
    int ans=1, num=0, mm=0, j, maxs=0, aim[maxn];
    while(~scanf("%d%d", &e[ans].x, &e[ans].y))
    {
        e[ans].id=ans;
        ans++;
    }
    sort(e+1, e+ans, cmp);
    for(j=1; j<ans; j++)
    {
        dp[j].first=1;
        dp[j].second=0;
    }
    for(j=1; j<ans; j++)
    {
        for(int k=1; k<j; k++)
        {
            if(e[j].x>e[k].x && e[j].y<e[k].y && dp[j].first<dp[k].first+1)
            {
                dp[j].first=dp[k].first+1;
                dp[j].second=k;
            }
        }
        if(maxs<dp[j].first)
        {
            maxs=dp[j].first;
            mm=j;
        }
    }
    printf("%d
", maxs);
    int m[1111], t=mm;
    for(j=1;j<=maxs;j++)
    {
        m[j]=t;
        t=dp[t].second;
    }
    for(int k=maxs;k>=1;k--)
        printf("%d
",e[m[k]].id);
    return 0;
}