HDU/HDOJ 1160 FatMouse’s Speed

题目传送门:

http://acm.hdu.edu.cn/showproblem.php?pid=1160

简单的DP,但是纠结了2个小时,因为在输出最长子序列路径时搞晕了,把pre和id搞混了。。。

代码很乱,懒的整理了~~

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include <iostream>
#include <conio.h>
 
using namespace std;
 
typedef struct Mouse{
    int weight;
    int speed;
    int id;
    int pre;
};
 
int cmp(const void *arg1, const void *arg2)
{
    Mouse *v1 = (Mouse*)arg1;
    Mouse *v2 = (Mouse*)arg2;
    if(v1->weight == v2->weight)
        return -(v1->speed - v2->speed);
    else
        return v1->weight - v2->weight;
}
 
 
Mouse mice[1005];
int dp[1005];
int que[1005];
int tt = 0;
 
int main()
{
    //freopen("input.txt", "r", stdin);
    int cnt = 0, p, q;
    while(cin >> p >> q)
    {
        mice[cnt].weight = p;
        mice[cnt].speed = q;
        mice[cnt].id = cnt;
        mice[cnt++].pre = -1;
 
    }
    qsort(mice, cnt, sizeof(Mouse), cmp);
 
 
    for(int i=0; i<cnt; ++i)
        dp[i] = 1;
    for(int i=1; i<cnt; ++i)
        for(int j=0; j<i; ++j)
            if(mice[i].weight>mice[j].weight && mice[i].speed<mice[j].speed)
            {
                if(dp[i] < dp[j]+1)
                {
                    dp[i] = dp[j]+1;
                    mice[i].pre = mice[j].id;
                }
            }
    int tmp = 0, tmp_id = 0;
    for(int i=0; i<cnt; ++i)
        if(dp[i] > tmp)
        {
            tmp = dp[i];
            tmp_id = i;
        }
    cout << tmp << endl;
    tmp = mice[tmp_id].id;
    ////////////////////////
    /*
    cout << "weight" << " " << "speed" << " " << "id" << " " << "pre" << endl;
    for(int i=0; i<cnt; ++i)
        cout << mice[i].weight << " " << mice[i].speed << " " << mice[i].id << " " << mice[i].pre << endl;
    */
 
    while(tmp != -1)
    {
        que[tt++] = tmp+1;
        for(int i=0; i<cnt; ++i)
            if(mice[i].id == tmp)
            {
                tmp = mice[i].pre;
            }
    }
    for(int i=tt-1; i>=0; --i)
        cout << que[i] << endl;
 
 
}

发布者

Tanky Woo

Tanky Woo,[个人主页:https://tankywoo.com] / [新博客:https://blog.tankywoo.com]

《HDU/HDOJ 1160 FatMouse’s Speed》有197个想法

发表评论

电子邮件地址不会被公开。 必填项已用*标注