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;
}

仅学习记录

加油变强！