【最长上升子序列LIS+路径记录】HDU-1160 FatMouse's Speed
程序员文章站
2022-07-03 21:45:18
...
注解
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;
}