[HAOI2007]上升序列

贪心 LIS

题面

求一个长度为$n$的序列长度为$L$的字典序最小（最靠前）的上升序列。

• $n\leq10000,Q\leq1000$

解析

我好像忘了怎么求最长上升子序列

$O(nlogn)$输出$LIS$

从后往前枚举位置，枚到一个新数字时，二分出它在已有（它后面的）最长上升序列的合适位置，把它插在最小的、比它大的数的后面（因序列中数按后面的序列长度从小到大、倒着存在数组里）。
这样能快速求出每个点后面$LIS$长度$f[i]$。

il int find(re int x)
{
  re int l=1,r=len,ans=0;
  while(l<=r)
    {
      re int mid=l+r>>1;
      if(b[mid]>a[x]) ans=mid,l=mid+1;
      else r=mid-1;
    }
  return ans;
}
il void Pre()
{
  fq(i,n,1)
    {
      f[i]=find(i)+1;
      b[f[i]]=a[i];
      len=max(len,f[i]);
    }
}

$100pts$算法

从前往后枚举$LIS$的第几个数字,若$f[i]+need\geq L$且该数大于上一个,即无脑将该数加入序列。
由于从前往后，因而最优。

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define re register
#define il inline
#define ll long long
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define fp(i,a,b) for(re int i=a;i<=b;i++)
#define fq(i,a,b) for(re int i=a;i>=b;i--)
using namespace std;
const int N=1e4+100;
int n,a[N],m,L,f[N],b[N],len;
il ll gi()
{
  re ll x=0,t=1;
  re char ch=getchar();
  while(ch!='-'&&(ch<'0'||ch>'9')) ch=getchar();
  if(ch=='-') t=-1,ch=getchar();
  while(ch>='0'&&ch<='9') x=x*10+ch-48,ch=getchar();
  return x*t;
}
int main()
{
  n=gi();
  fp(i,1,n) a[i]=gi();
  Pre();
  m=gi();
  while(m--)
    {
      L=gi();
      if(L>len) {puts("Impossible");continue;}
      re int las=0;
      fp(i,1,n)
    if(f[i]>=L&&a[i]>a[las])
      {
        printf("%d ",a[i]);
        las=i;
        if(!(--L)) {puts("");break;}
      }
    }
  return 0;
}