AT_joisc2015_e

题意

给定长为 \(n-1\) 的数组 \(b_i\)，要求有多少长为 \(n\) 的数组 \(a_i\) 满足：

\(b\) 数组可以由 \(a\) 数组删掉一个数得到。
存在一个排列 \(p\) 满足 \(a_i\) 是以 \(p_i\) 结尾的最长上升子序列长度。

思路

可能算是结论题。

首先考虑如果我们知道了 A 数组，如何判断是否合法。可以发现条件是 \(a_i\le premax_{i-1}+1\)。

证明的话可以考虑设 \(a_i=k\)，我们取 \(a_j=k-1\) 的最大的 \(j\)，只要将 \(h_i\) 设为比 \(h_j\) 稍大，即 \(i,j\) 中间不存在 \(k\) 满足 \(h_j<h_k<h_i\) 即可，这是容易实现的。

然后考虑计数。

如果存在一个位置 \(i\) 使得 \(b_i>premax_{i-1}+2\)，那么显然无解。
如果存在一个位置 \(i\) 使得 \(b_i=premax_{i-1}+2\)，那么只能有一个这样的位置，同时 \(premax_{i-1}\) 这个数可以填在最小的满足 \(b_j=premax_{i-1}\) 的 \(j\) 和 \(i\) 之间的位置。
否则除开最后一个位置，每个位置 \(i\) 前有 \(premax_{i-1}\) 个数可以填（不 +1 是为了防止有重复），最后一个位置可以填 \(premax_{n-1}+1\) 个数，累加起来就是答案。

复杂度 \(O(n)\)。

代码比较简单：

const int N=1005001;
int n,a[N];
int main(){
    n=read();
    for(int i=1;i<n;i++)a[i]=read();
    long long ans=0;
    int maxn=0,pos=0;
    for(int i=1;i<n;i++){
        if(a[i]-maxn>2){
            cout<<0<<endl;
            return 0;
        }
        if(a[i]-maxn==2){
            maxn=a[i];
            for(int j=i+1;j<n;j++){
                if(a[j]-maxn>1){
                    cout<<0<<endl;
                    return 0;
                }
                maxn=max(maxn,a[j]);
            }
            cout<<i-pos<<endl;
            return 0;
        }
        ans+=maxn;
        if(a[i]>maxn)maxn=a[i],pos=i;
    }
    cout<<ans+maxn+1<<endl;
    return 0;
}