Hdu-1160 FatMouse's Speed（lis打印路径）

本文主要是介绍Hdu-1160 FatMouse's Speed（lis打印路径），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

FatMouse’s Speed（lis打印路径）

hdu-1160

lis打印路径，结构体先排序一次
注意pos数组的更新及取出

ac代码（nlogn)：

#include<bits/stdc++.h>
#pragma GCC optimize(2)
#define IOS ios_base::sync_with_stdio(0); cin.tie(0);
#define ll long long
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=1e6;
int dp[maxn],pos[maxn],ans[maxn]={0};
int n,len;struct Node{int w,s,cnt;
}a[1010];int cmp(Node s,Node b){return s.w>b.w;
}int main(){n=1;while(cin>>a[n].w>>a[n].s){a[n].cnt=n;n++;}n--;//cout<<n<<endl;sort(a+1,a+n+1,cmp);/*for(int i=1;i<=n;i++){cout<<a[i].w<<" "<<a[i].s<<" "<<a[i].cnt<<endl;}*/dp[1]=a[1].s;len=1;pos[1]=len;for(int i=2;i<=n;i++){if(a[i].s>=dp[len]){dp[++len]=a[i].s;pos[i]=len;}else{int tem=upper_bound(dp,dp+len,a[i].s)-dp;dp[tem]=a[i].s;pos[i]=tem;}}cout<<len<<endl;int maxx=INF;//找pos数组的起源位置；for(int i=n;i>0;i--){if(!len){break;}if(pos[i]==len && maxx>=a[i].s){ans[len]=i;//此处即为位置cout<<a[ans[len]].cnt<<endl;//输出位置对应的序号即可；len--;maxx=a[i].s;}}return 0;
}

仅学习记录

加油变强！

这篇关于Hdu-1160 FatMouse's Speed（lis打印路径）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---