HDU 1160 FatMouse's Speed（要记录路径的二维LIS）

时间：2021-04-15 06:09:25

FatMouse's Speed

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 14980    Accepted Submission(s): 6618
Special Judge

Problem Description
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.
 
Input
Input contains data for a bunch of mice, one mouse per line, terminated by end of file.

The data for a particular mouse will consist of a pair of integers: the first representing its size in grams and the second representing its speed in centimeters per second. Both integers are between 1 and 10000. The data in each test case will contain information for at most 1000 mice.

Two mice may have the same weight, the same speed, or even the same weight and speed.

 
Output
Your program should output a sequence of lines of data; the first line should contain a number n; the remaining n lines should each contain a single positive integer (each one representing a mouse). If these n integers are m[1], m[2],..., m[n] then it must be the case that

W[m[1]] < W[m[2]] < ... < W[m[n]]

and

S[m[1]] > S[m[2]] > ... > S[m[n]]

In order for the answer to be correct, n should be as large as possible.
All inequalities are strict: weights must be strictly increasing, and speeds must be strictly decreasing. There may be many correct outputs for a given input, your program only needs to find one.

 
Sample Input
6008 1300
6000 2100
500 2000
1000 4000
1100 3000
6000 2000
8000 1400
6000 1200
2000 1900
 
Sample Output
4
4
5
9
7
 

题目链接：HDU 1160

比较裸的二维LIS，但是WA了无数次， 好像是把id和下标搞混了………………，由于题目说重量weight要递增的情况下speed要递减，显然是先对weight进行排序再按speed关键字找最长严格下降子序列，但这样不符合个人习惯……于是就换了一下按weight递减，speed递增，找最长严格上升子序列，显然当weight相同时要把speed小的排前面，然后记录每一个可能组成LIS的老鼠的前驱，由于顺序是反着找的，最后回溯出来的顺序就是答案了，不用放到栈里，但由于要统计最长的个数，还是放到队列里方面。我这个代码出来的样例答案是 4 4 5 6 1，也是符合题意的

代码：

#include <stdio.h>

#include <bits/stdc++.h>

using namespace std;

#define INF 0x3f3f3f3f

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

typedef pair<int,int> pii;

typedef long long LL;

const double PI=acos(-1.0);

const int N=1010;

struct info

{

    int speed;

    int weight;

    int pre;

    int id;

    bool operator<(const info &t)const

    {

        return (weight>t.weight||(weight==t.weight&&speed<t.speed));

    }

};

info arr[N];

int dp[N];

int main(void)

{

    int w,s,i,j;

    int cnt=0;

    while (~scanf("%d%d",&w,&s))

    {

        arr[cnt].id=cnt+1;

        arr[cnt].pre=-1;

        arr[cnt].weight=w;

        arr[cnt].speed=s;

        ++cnt;

    }

    sort(arr,arr+cnt);

    CLR(dp,0);

    for (i=0; i<cnt; ++i)

    {

        int tpre=-1;

        int pre_max=0;

        for (j=0; j<i; ++j)

        {

            if(dp[j]>pre_max&&arr[j].speed<arr[i].speed&&arr[j].weight>arr[i].weight)

            {

                pre_max=dp[j];

                tpre=j;

            }

            dp[i]=pre_max+1;

            arr[i].pre=tpre;

        }

    }

    int indx=max_element(dp,dp+cnt)-dp;

    queue<int>pos;

    while (indx!=-1)

    {

        pos.push(arr[indx].id);

        indx=arr[indx].pre;

    }

    printf("%d\n",pos.size());

    while (!pos.empty())

    {

        printf("%d\n",pos.front());

        pos.pop();

    }

    return 0;

}

相关文章