链接:

https://vjudge.net/problem/HDU-1160

题意:

FatMouse believes that the fatter a mouse is, the faster it runs. To disprove this, you want to take the data on a collection of mice and put as large a subset of this data as possible into a sequence so that the weights are increasing, but the speeds are decreasing.

思路:

对s排序, 然后最长递增子序列,nlogn总有bug还是n2好用

代码:

#include <iostream>

#include <cstdio>

#include <cstring>

#include <vector>

//#include <memory.h>

#include <queue>

#include <set>

#include <map>

#include <algorithm>

#include <math.h>

#include <stack>

#include <string>

#include <assert.h>

#include <iomanip>

#include <iostream>

#include <sstream>

#define MINF 0x3f3f3f3f

using namespace std;

typedef long long LL;

const LL MOD = 20090717;

const int MAXN = 1e3+10;

struct Node

{

    int w, s;

    int id;

    bool operator < (const Node& that) const

    {

        return this->s > that.s;

    }

}node[MAXN];

int Dp[MAXN], Pre[MAXN];

int n;

void Print(int p)

{

    if (p == -1)

        return;

    Print(Pre[p]);

    printf("%d\n", node[p].id);

}

int main()

{

    int l, r;

    while (~scanf("%d%d", &l, &r))

    {

        node[++n].w = l;

        node[n].s = r;

        node[n].id = n;

    }

    sort(node+1, node+1+n);

    memset(Pre, -1, sizeof(Pre));

    memset(Dp, 0, sizeof(Dp));

    for (int i = 1;i <= n;i++)

    {

        Dp[i] = 1;

        for (int j = 1;j < i;j++)

        {

            if (node[i].w > node[j].w && node[i].s < node[j].s)

            {

                if (Dp[j]+1 > Dp[i])

                {

                    Dp[i] = Dp[j]+1;

                    Pre[i] = j;

                }

            }

        }

    }

    int maxval = 1, maxpos = 1;

    for (int i = 1;i <= n;i++)

    {

        if (maxval < Dp[i])

        {

            maxval = Dp[i];

            maxpos = i;

        }

    }

    printf("%d\n", maxval);

    Print(maxpos);

    return 0;

}