HDU 1160 FatMouse's Speed

题目链接：[kuangbin带你飞]专题十二 基础DP1 J - FatMouse’s Speed

题意

给n个老鼠的体重和速度，求找出一个最长的序列，此序列体重递增速度递减

思路

按体重递增排序，再求最长递增(此递增表示体重递增速度递减)子序列。
dp[i] = max(dp[j]+1) 0<=j<=i-1

代码

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

const int N = 1006;
struct Node
{
    int a, b, i;
    bool operator <(const Node &t) const
    {
        return a < t.a;
    }
}p[N];

int dp[N], fa[N], ans[N];

int main()
{
    int pos = 0;
    while(~scanf("%d%d", &p[pos].a, &p[pos].b))
    {
        p[pos].i = pos+1;
        pos++;
    }
    sort(p, p+pos);
    memset(fa, -1, sizeof(fa));
    int ians = 0, amax = 0;
    for(int i=0; i<pos; i++)
    {
        int mmax = 0;
        for(int j=0; j<i; j++)
        {
            if(p[j].a < p[i].a && p[j].b > p[i].b && mmax < dp[j])
            {
                mmax = dp[j];
                fa[i] = j;
            }
        }
        dp[i] = mmax+1;
        if(amax < dp[i])
        {
            amax = dp[i];
            ians = i;
        }
    }
    printf("%d\n", amax);
    int i = 0;
    while(i < amax)
    {
        ans[i++] = p[ians].i;
        ians = fa[ians];
    }
    while(i--)
        printf("%d\n", ans[i]);
    return 0;
}