[COCI2021-2022#1] Volontiranje 题解

· · 题解

前置芝士

LIS 的 nlog(n) 算法

也就是说您可以去看看这道博客

题解

长度直接求就好了，现在考虑怎么求方案数。

我们把题目所给的序列中的每一个元素按照下标和值表示成一个点对，然后建立平面直角坐标系(x 为下标，y 为值，这里以样例 3 举例):

我们发现，一个上升子序列反应到图上是由 x，y 均递增的点组成的，且任意组 x 递增，y 递减的点一定不是上升子序列。

我们考虑从 x=1 开始，将这些点划分成多组 x 递增，y 递减的点，如图:

那么可以发现，任意一个最长上升子序列方案都可以表现为在每一层中分别选择一个点且满足它们均是 x，y 均递增的点的前提下的方案。

以样例 3 为例，其中的一个最长上升子序列的方案为 1 3 5 ，反应在坐标系上就是选择 A C E 三个点。

那么这个问题就神奇的转换成了：在每一层中选一个点，在满足它们均是 x，y 均递增的点的情况下且每个点只能选一次的方案数。

我们先解决怎么分层。

我们将 LIS_i 定义为在下标 i 处结束的最长递增子序列的长度,那么其实第 k 层就是 LIS_i=k 的下标的集合。

然后我们接下来证明一个问题：在某一层中的点跳到下一层中时，选择下标更小的点一定不劣于选择下标更大的点。

让我们再来看一看那张图：

举个例子，我现在已经选择了 A 点，下一步可以选择 C，D 点，但我选择 C 点的总方案数一定不比选择 D 点的方案数少。

我们考虑怎么证明。

以这里的 A,B,C,D 举例，如果我们选择 A,D，那么还有 B,C 这一条路；如果我们选择 A,C，那么还有 B,D 这一条路。推广到很多个，我们的选择一定不会导致答案变小

但是为什么不能用 A,D，B,C 这样交错的方法呢？

以这张图为例，如果我们选择 A,D, 会发现 B,C 无法选择，但我们可以选择 A,C B,D 这两种方法。推广一下，我们的方法一定是最优的。

代码

#include<bits/stdc++.h>
using namespace std;

int n,len=0;
int a[1000005];
int dp[1000005];
int id[1000005];
vector<int> v[1000005],st;
vector<vector<int> > ans;
//int ans=0x3f3f3f3f;

void File(){
    freopen("volunteering.in","r",stdin);
    freopen("volunteering.out","w",stdout);
}

void Solve(){
    while(1){
        if(st.empty())
            if(v[1].empty()) break;
            else st.push_back(v[1].back()),v[1].pop_back();
        else if(st.size()==len) ans.push_back(st),st.clear();
        else{
            int k=st.size()+1,now=st.back();
            while (v[k].size()&&v[k].back()<now) v[k].pop_back();
            if(v[k].empty()||a[now]>a[v[k].back()]) st.pop_back();
            else st.push_back(v[k].back()),v[k].pop_back();
        }
    }
}

int main(){
    cin>>n;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        if(dp[len]<a[i]){ ++len;dp[len]=a[i],id[len]=i;v[len].push_back(i);continue; }
        int now=lower_bound(dp+1,dp+len+1,a[i])-dp;
        dp[now]=a[i],id[now]=i;
        v[now].push_back(i); 
    }
    for(int i=1;i<=len;i++) reverse(v[i].begin(),v[i].end());
    Solve();
    printf("%d %d\n",ans.size(),len);
    for(int i=0;i<ans.size();i++){
        for(auto x:ans[i]) printf("%d ",x);
        printf("\n"); 
    }
    return 0;
} 
/*
14
9 12 8 3 5 4 13 1 14 10 6 2 11 7

7
2 1 6 5 7 3 4
*/