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