题解：P14409 [JOISC 2015] 建筑装饰 3 / Building 3

Austin0116 · 2025-12-05 15:36:17 · 题解

分析

这道题较为简单，首先根据最长上升子序列的性质，考虑 a 数组的限制，1 \le a_i \le i，对于任意断点，前一段的最大值和后一段的最小值相差不超过 1。那么我们就可以先判无解，就是有 b_i \ge i+2 或存在一个断点，使得前一段的最大值和后一段的最小值相差大于等于 3。当然，若存在至少两个以下情况：有 b_i \ge i+1，存在一个断点，使得前一段的最大值和后一段的最小值相差等于 2 也是无解。

接下来考虑有些前缀必填一些数的情况，就是出现一次以下情况：有 b_i \ge i+1，存在一个断点，使得前一段的最大值和后一段的最小值相差等于 2。设断点为 i，后一段最小值或 a_i 为 x，则答案为：

最后再考虑其他一般情况，我们只需要满足上述两个性质即可。

代码

#include <bits/stdc++.h>
#define N 1000005
#define ll long long
using namespace std;
int n,a[N],mn[N],mx,fl,id; 
ll sum; 
int main(){
    scanf("%d",&n);
    n--;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<=n;i++){
        if(a[i]>i+1||mx<a[i]-1){
            if(a[i]-i>=3||mx<a[i]-2) fl=2;
            else if(id) fl=2;
            else id=i;
        } 
        if(fl>=2) break; 
        mx=max(mx,a[i]);
    }//判无解
    if(fl>=2){ 
        putchar('0');
        exit(0);
    }//无解
    if(id){
        mx=0;
        for(int i=1;i<=id;i++){
            if(a[id]-1<=i&&mx+1>=a[id]-1) sum++;
            mx=max(mx,a[i]);
        }
        printf("%lld",sum);
        exit(0);
    }//第二种情况
    mx=0;
    for(int i=0;i<=n;i++){
        sum+=min(i+1,mx+1);
        sum-=(i&&fl&&a[i]<=min(i+1,mx+1));
        if(a[i+1]<=min(i+1,mx+1)) fl=1;
        else if(i&&a[i+1]==a[i]) ;
        else fl=0;
        mx=max(mx,a[i+1]); 
    }//一般情况
    printf("%lld",sum); 
    return 0;
}