欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed

程序员文章站 2022-07-03 21:45:18
...

【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed
【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed
【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed

注解

1、最长上升子序列的变形。先按照题目要求,根据weight升序和speed降序排序,然后是利用最长上升子序列LIS算法,找到符合要求的最长序列。
2、利用pre数组记录路径。

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

struct Mouse {
    int id;
    int w;
    int sp;
};

const int INF = 2e9;
const int MAXN = 1e3+10;
Mouse mouse[MAXN];
int dp[MAXN];
int pre[MAXN];

int cmp(Mouse m1, Mouse m2) {
    if(m1.w!=m2.w) {
        return m1.w<m2.w;
    } else {
        if(m1.sp!=m2.sp) {
            return m1.sp>m2.sp;
        } else {
            return m1.id<m2.id;
        }
    }
}

void Print(int k) {
    if(!k)
        return;
    Print(pre[k]);
    cout<<mouse[k].id<<endl;
}

int main() {

    int n = 1;
    while(cin>>mouse[n].w>>mouse[n].sp) {
        mouse[n].id = n;
        n++;
    }
    sort(mouse+1, mouse+n, cmp);
    mouse[0].w = -INF;
    mouse[0].sp = INF;
    memset(dp, 0, sizeof(dp));
    memset(pre, 0, sizeof(pre));

    int k = -1;
    for(int i=1; i<n; i++) {
        for(int j=0; j<i; j++) {
            if(mouse[i].w>mouse[j].w &&
                mouse[i].sp<mouse[j].sp &&
                dp[i]<dp[j]+1) {
                dp[i] = dp[j]+1;
                pre[i] = j;
            }
            if(k==-1 || dp[i]>dp[k]) {
                k = i;
            }
        }
    }

    cout<<dp[k]<<endl;
    Print(k);

    return 0;
}

结果

【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed