HDU 1160(类似于最长上升子序列)

短命女 2022-09-20 11:22 29阅读 0赞

题意：给出一连串老鼠的体重和速度，求最长的序列符合老鼠体重是严格递增，而速度是严格递减。

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    using namespace std;
    
    #define MAX(a, b) ((a) > (b) ? (a) : (b))
    
    struct Mice
    {
        int weight, speed, mark;
        Mice() {}
        Mice(int w, int s, int m) : weight(w), speed(s), mark(m) {}
        bool operator <(const Mice& rhs) const
        {
            if (weight == rhs.weight)
                return speed > rhs.speed;
            return weight < rhs.weight;
        }
    } mice[1009];
    int cnt;
    
    int F[1009];
    int last[1009];
    
    void print(int sub)
    {
        if (sub != -1)
        {
            print(last[sub]);
            printf("%d\n", mice[sub].mark);
        }
    }
    
    int main()
    {
        int w, s, i, j, max, max_sub;
        cnt = 0;
        while (scanf("%d%d", &w, &s) != EOF)
        {
            mice[cnt] = Mice(w, s, cnt+1);
            cnt += 1;
        }
        sort(mice, mice+cnt);
        max = F[0] = 1, last[0] = -1, max_sub = 0;
        for (i = 1; i < cnt; ++i)
        {
            F[i] = 1, last[i] = -1;
            for (j = 0; j < i; ++j)
            {
                if (mice[i].weight > mice[j].weight && mice[i].speed < mice[j].speed && F[i] < F[j] + 1)
                    F[i] = F[j] + 1, last[i] = j;
            }
            if (max < F[i])
                max = F[i], max_sub = i;
        }
        printf("%d\n", max);
        print(max_sub);
        return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，29人围观）

还没有评论，来说两句吧...

相关阅读

相关最长上升子序列

最长上升子序列 1、参考资料 https://leetcode-cn.com/problems/longest-increasing-subsequence/ h

- 日理万妓/ 2022年12月04日 07:57/ 0 赞/ 261 阅读

相关 HDU 1160(类似于最长上升子序列)

题意：给出一连串老鼠的体重和速度，求最长的序列符合老鼠体重是严格递增，而速度是严格递减。 include <cstdio> include <cstr

短命女/ 2022年09月20日 11:22/ 0 赞/ 30 阅读

相关 hdu1160 最大上升子序列问题+输出路径

题意：就是在一个序列里面找出最长的子序列，这个序列中体积上升，速度下降。分析：就是按体积排序之后素的的找出最大下降子序列就可以了，麻烦一点的就是需要输出顺

清疚/ 2022年08月20日 15:08/ 0 赞/ 173 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < ... < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, ...,

川长思鸟来/ 2022年07月13日 01:55/ 0 赞/ 233 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

港控/mmm°/ 2022年07月12日 02:47/ 0 赞/ 261 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b 1 < b 2 < ... < b S的时候，我们称这个序列是上升的。对于给定的一个序列(a 1, a 2

墨蓝/ 2022年07月12日 02:47/ 0 赞/ 291 阅读

相关最长上升子序列

严格上升和非严格上升的 include <iostream> using namespace std; int main() {

柔光的暖阳◎/ 2022年06月15日 09:52/ 0 赞/ 347 阅读

相关 HDU 1160(动态规划-最长上升子序列)

问题描述： FatMouse believes that the fatter a mouse is, the faster it runs. To disprove thi

谁借莪１个温暖的怀抱￠/ 2022年06月03日 07:07/ 0 赞/ 232 阅读

相关最长上升子序列

最长上升子序列 Time Limit: 3000 ms Memory Limit: 65536 KiB Submit Statistic Discuss Probl

傷城~/ 2022年05月30日 10:09/ 0 赞/ 247 阅读

相关最长上升子序列

Problem Description 一个数的序列bi，当b1 < b2 < … < bS的时候，我们称这个序列是上升的。对于给定的一个序列(a1, a2, …, aN)

一时失言乱红尘/ 2022年05月16日 01:28/ 0 赞/ 287 阅读