codeforces mysterious present 最长上升子序列+倒序打印路径

link:http://codeforces.com/problemset/problem/4/D

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cctype>
#include <algorithm>
#include <queue>
#include <deque>
#include <queue>
#include <list>
#include <map>
#include <set>
#include <vector>
#include <utility>
#include <functional>
#include <fstream>
#include <iomanip>
#include <sstream>
#include <numeric>
#include <cassert>
#include <ctime>
#include <iterator>
const int INF = 0x3f3f3f3f;
const int dir[8][2] = {{-1,0},{1,0},{0,-1},{0,1},{-1,-1},{-1,1},{1,-1},{1,1}};
using namespace std;
int n,w,h,cnt,ans,d[5009],path[5009],End;
bool flag;
typedef struct node
{
    int W,H,In;
    bool operator < (const node &other) const
    {
        if(W!=other.W) return W<other.W;
        else return H<other.H;
    }
}node;
node ma[5009];
bool judge(node a,node b)
{
    if(a.W<b.W&&a.H<b.H) return true; else return false;
}
void print_ans(int i)
{
    if(i==-1) return;
    print_ans(path[i]);
    printf("%d ",ma[i].In+1);
}
int main(void)
{
    #ifndef ONLINE_JUDGE
    freopen("in.txt", "r", stdin );
    #endif // ONLINE_JUDGE

    while(~scanf("%d%d%d",&n,&w,&h))
    {
        flag=false; cnt=0;
        for(int i=0;i<n;++i)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a<=w||b<=h) continue;
            flag=true; ma[cnt].W=a; ma[cnt].H=b; ma[cnt].In=i;
            cnt++;
        }
        if(!flag)
        {
            printf("0\n"); continue;
        }
        sort(ma,ma+cnt);
        ans=1;
        memset(d,0,sizeof(d));
        memset(path,-1,sizeof(path));
        End=0;
        for(int i=0;i<cnt;++i) d[i]=1;
        for(int i=1;i<cnt;++i)
        {
            int tmp=0;
            for(int j=0;j<i;++j)
            {
                if(judge(ma[j],ma[i]))
                {
                    if(tmp<d[j])
                    {
                        tmp=d[j]; path[i]=j;
                    }
                }
            }
            d[i]=tmp+1;
            if(ans<d[i])
            {
                ans=d[i]; End=i;
            }
        }
        printf("%d\n",ans);
        print_ans(End);
        printf("\n");
//        printf("%d\n",ma[End-1].In+1);
    }

    return 0;
}

最长上升子序列还写这么挫哦

这两天沉迷于kpw……囧