J - FatMouse's Speed HDU - 1160——基础dp

我不是女神ヾ 2022-06-10 03:41 87阅读 0赞

Think:  
1知识点：排序+最长上升子序列+记录路径  
2题意：寻找一个最长子串，使得重量w严格递增，速度c严格递减  
3反思：注意排序后的路径记录和通过递归回溯输出路径

[vjudge题目链接][vjudge]

以下为Accepted代码

#include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    struct Node{
        int w, c;
        int pos;/*存储初始路径结点*/
        bool operator < (const Node &b) const {
            return c > b.c;
        }
    }node[1014];
    
    struct DP{
        int num;
        int next;/*记录回溯标记结点*/
        int pos;/*存储初始路径结点*/
    }dp[1014];
    
    void Pri_path(int x);/*通过递归回溯输出路径*/
    
    int main(){
        int tp, i, j, mav, v, ans, x;
        tp = 1;
        while(~scanf("%d %d", &node[tp].w, &node[tp].c)){
            node[tp].pos = tp;
            tp++;
        }
    
        sort(node+1, node+tp);
        for(i = 0; i <= tp; i++){
            dp[i].num = 0, dp[i].next = -1;
        }
    
        ans = 0, x = -1;
        for(i = 1; i <= tp; i++){
            mav = 0, v = -1;
            for(j = 1; j < i; j++){
                if(node[j].w < node[i].w && node[j].c > node[i].c && dp[j].num > mav){
                    mav = dp[j].num, v = j;
                }
            }
            dp[i].num = mav + 1;
            dp[i].next = v;
            dp[i].pos = node[i].pos;
            if(dp[i].num > ans){
                ans = dp[i].num, x = i;
            }
        }
        printf("%d\n", ans);
        Pri_path(x);
        return 0;
    }
    void Pri_path(int x){
        if(dp[x].next != -1){
            Pri_path(dp[x].next);
        }
        printf("%d\n", dp[x].pos);
    }

[vjudge]: https://vjudge.net/contest/163018#problem/J