HDU 1160 FatMouse's Speed

简单DP，最长上升子序列。先对W排序，然后对S做做LIS

#include<cstdio>
#include<cstring>
#include<cmath>
#include<stack>
#include<vector>
#include<algorithm>
using namespace std;

const int maxn=10000+10;
struct X
{
    int w,s;
    int id;
} x[maxn];

bool cmp(const X&a,const X&b)
{
    return a.w<b.w;
}

int pre[maxn],dp[maxn];
stack<int>S;

int main()
{
    int n=0;
    while(~scanf("%d %d",&x[n].w,&x[n].s))
    {
        x[n++].id=n+1;
    }
    while(!S.empty())S.pop();

    sort(x,x+n,cmp);

    memset(dp,1,sizeof dp);
    memset(pre,-1,sizeof pre);

    for(int i=0; i<n; i++)
    {
        int Max=0,Pos=-1;
        for(int j=0; j<i; j++)
        {
            if(x[j].w<x[i].w)
            {
                if(x[j].s>x[i].s)
                {
                    if(dp[j]>Max)
                    {
                        Max=dp[j];
                        Pos=j;
                    }
                }
            }
        }
        dp[i]=Max+1;
        pre[i]=Pos;
    }

    int ans=0,ansPos=-1;
    for(int i=0; i<n; i++)
    {
        if(dp[i]>ans)
        {
            ans=dp[i];
            ansPos=i;
        }
    }

    int nowPos=ansPos;
    while(1)
    {
        S.push(nowPos);
        nowPos=pre[nowPos];
        if(nowPos==-1) break;
    }

    printf("%d
",ans);
    while(!S.empty())
    {
        printf("%d
",x[S.top()].id);
        S.pop();
    }

    return 0;
}