【題目敘述】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;
}