P2766 最长不下降子序列问题 题解——杨表毁天灭地
masterhuang
·
·
题解
前置知识：杨表
首先有个网络流做法，但是发现它太不牛了。
考虑 选取若干不交 LIS 这件事，这相当于啥呢？
相当于询问杨表有多少行和第一行长度一样。
于是前两问你建出 a_1,a_2,\cdots,a_n 的杨表。
-
第一问答案是杨表第一行长度
-
第二问答案是杨表有多少行长度能和第一行相等。
考虑第三问：相当于你让 a_1 变成 a_1,a_1-\epsilon,a_1-2\epsilon,\cdots,a_1-(n-1)\epsilon
$\epsilon$ 你就先让 $a$ 全局扩大 $n$ 倍，然后令 $\epsilon=1$ 即可。
注意当 **LIS** 长度为 $1,2$ 的时候不能这样做，要特判。
杨表插入单次 $O(n\log n)$，总复杂度 $O(n^2\log n)$。
```cpp
#include<bits/stdc++.h>
#define LL long long
#define fr(x) freopen(#x".in","r",stdin);freopen(#x".out","w",stdout);
using namespace std;
const int N=1505;
int n,a[N];multiset<int>S[N];
priority_queue<int,vector<int>,greater<int>>q;
inline void ins(int x)
{
for(int i=1;;i++)
{
S[i].insert(x);
auto t=S[i].upper_bound(x);
if(t==S[i].end()) break;
x=*t;S[i].erase(t);
}
}//杨表插入
int main()
{
ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);cin>>n;
for(int i=1;i<=n;i++) cin>>a[i],ins(a[i]);
cout<<S[1].size()<<"\n";int c=0;
for(int i=1;S[i].size()==S[1].size();i++) c++;
cout<<c<<"\n";
if(S[1].size()==1) return cout<<c,0;
if(S[1].size()==2)
{
c=(a[1]<=a[n]);
for(int i=2;i<n;i++)
{
if(a[1]<=a[i]||a[i]<=a[n]) c++;
else if(q.size()&&a[i]>=q.top()) c++,q.pop();
else q.push(a[i]);
}
return cout<<c,0;
}c=0;//特判
for(int i=1;i<=n;i++) S[i].clear();
for(int i=0;i<n;i++) ins(a[1]*n-i);//加入 a[1]-epsilon
for(int i=2;i<n;i++) ins(a[i]*n);
for(int i=0;i<n;i++) ins(a[n]*n-i);
for(int i=1;S[i].size()==S[1].size();i++) c++;
cout<<c<<"\n";//和问题 2 一样求解
return 0;
}
```