HDU - 1160 FatMouse's Speed 动态规划LIS,路径还原与nlogn优化

HDU - 1160

给一些老鼠的体重和速度

要求对老鼠进行重排列,并找出一个最长的子序列,体重严格递增,速度严格递减

并输出一种方案

原题等于定义一个偏序关系 $(a,b)<(c.d)$ 当且仅当 $a<c,b>d$ 然后找出最长链

...我们就按照他说的重新排个序,然后找LIS吧,不过还需要去路径还原

数据量可以用$O(n^2)$的算法

不过我这里用来$O(nlogn)$的算法加上一个路径还原

嗯,其实是在一个单调栈上乱搞的二分罢了....

最后要回溯一下并且记录答案才行

#include <bits/stdc++.h>

#define ll long long

#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)

#define pp pair<int,int>

#define rep(ii,a,b) for(int ii=a;ii<=b;ii++)

#define per(ii,a,b) for(int ii=a;ii>=b;ii--)

#define show(x) cout<<#x<<"="<<x<<endl

#define show2(x,y) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<endl

#define show3(x,y,z) cout<<#x<<"="<<x<<" "<<#y<<"="<<y<<" "<<#z<<"="<<z<<endl

#define showa(b,a) cout<<#a<<"["<<b<<"]="<<a[b]<<endl;

using namespace std;

const int maxn=1e5+10;

const int maxm=1e6+10;

const int INF=0x3f3f3f3f;

int casn,n,m,k;

struct node {

	int a,b,id;

	int operator <(node x){

		if(x.a==a) return b>x.b;

		else return a<x.a;

	}

}ms[maxn];

int pre[maxn];

int stk[maxn],top;

int ans[maxn];

int main(){

//#define test

#ifdef test

    freopen("in.txt","r",stdin);freopen("out.txt","w",stdout);

#endif

	while(cin>>ms[n].a>>ms[n].b){ms[n].id=n+1;n++;}

	sort(ms,ms+n);

	memset(stk,0xc0,sizeof stk);

	rep(i,0,n-1) ms[i].b=-ms[i].b;

	rep(i,0,n-1){

		int b=ms[i].b;

		if(stk[top]<b){

			stk[++top]=b;

			pre[i]=top;

		}else {

			int l=1,r=top;

			while(l<r){

				int mid=(l+r)>>1;

				if(stk[mid]<b)l=mid+1;

				else r=mid;

			}

			stk[l]=b;

			pre[i]=l;

		}

	}

	cout<<top<<endl;

	int t=top;

	per(i,n,0){

		if(pre[i]==t) ans[--t]=ms[i].id;

		if(t<0) break;

	}

	rep(i,0,top-1) cout<<ans[i]<<endl;

#ifdef test

    fclose(stdin);fclose(stdout);system("gedit ./out.txt");

#endif

    return 0;

}