【題解】HDU 1160 FatMouse’s Speed

【題目敘述】https://vjudge.net/problem/HDU-1160
【解題想法】DP、LIS

  • 題目要求找出盡可能多的反例,來說明老鼠的體重和速度成反比。
  • 讀入測資後,先針對體重由小到大排序。
  • 目標要找出速度的最長「遞減」子序列。題目要求嚴格遞減。
  • 循序檢查每一隻老鼠,並與其前面的老鼠比較。只要符合體重增加但速度卻下降,就更新dp[ ]。
  • dp[i]:紀錄檢查到第 i 隻老鼠時的最長「遞減」速度序列。
  • pre[i]:紀錄其前一筆比較對象(dp更新的路徑)。
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
using namespace std;
#define pii pair<int,int>

struct Mouse {
    int w, s, idx; //weight, spees, ID
};

bool cmp(Mouse x, Mouse y){
    return x.w < y.w; //重量由小排到大
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n = 0;
    int w, s;
    vector <Mouse> v;
    while(cin >> w >> s){
        v.push_back({w, s, ++n});
    }
    sort(v.begin(),v.end(),cmp);
    
    int dp[n+5];
    int pre[n+5];
    
    for (int i=0; i<n; i++){
        pre[i] = -1;
        dp[i] = 1;
    }
    
    int mx = 0;
    for (int i=0; i<n; i++){
        for (int j=0; j<i; j++){
            if (v[i].w > v[j].w && v[i].s < v[j].s && dp[j] + 1 > dp[i]){
                dp[i] = dp[j] + 1;
                pre[i] = j;
            }
        }
        if (dp[i] > dp[mx]){
            mx = i;
        }
    }
    vector<int>ans;
    while (~mx){
        ans.push_back(v[mx].idx);
        mx = pre[mx];
    }
    reverse(ans.begin(), ans.end());
    cout << ans.size() << '\n';
    for(auto i: ans){
        cout << i << '\n';
    }
    return 0;
}

分享本文 Share with friends