CF1693D Decinc Dividing

· · 题解

一个有神奇性质的 DP 题

考虑如何

首先给出一个很别扭的定义

$ \mathit{dp_{i,1}} $ 为第 $ i $ 个元素在 **递减** 序列中时， **递増** 序列最后一个元素的 **最小值** 初始时候所有 $ \mathit{dp_{i,0}}=- \infty $ $ \mathit{dp_{i,1}}= \infty \mathit{dp_{1,0}}= \infty $ $ \mathit{dp_{1,1}}= - \infty

怎么转移？

枚举第 (i-1) 个元素是在递增序列还是递减序列，然后尝试更新 \mathit{dp_{i,1,0}} ，其实就是分类讨论

只要 \mathit{dp_{n,0}} \neq - \infty 或者 \mathit{dp_{n,1}} \neq \infty 那么就存在合法方案

bool check(int l,int r){
    for(int i=l;i<=r;++i)dp[i][0]=-inf;dp[l][0]=inf;
    for(int i=l;i<=r;++i)dp[i][1]=inf;dp[l][1]=-inf;
    for(int i=l;i<=r;++i){
        if(dp[i-1][0]!=-inf){//a[i-1]能在递增末尾
            if(a[i]>a[i-1])dp[i][0]=max(dp[i][0],dp[i-1][0]);//a[i]接在递增末尾
            if(a[i]<dp[i-1][0])dp[i][1]=min(dp[i][1],a[i-1]);//a[i]接在递减末尾
        }
        if(dp[i-1][1]!=inf){//a[i-1]能在递减末尾
            if(a[i]<a[i-1])dp[i][1]=min(dp[i][1],dp[i-1][1]);//a[i]接在递减末尾
            if(a[i]>dp[i-1][1])dp[i][0]=max(dp[i][0],a[i-1]);//a[i]接在递增末尾
        }
    }
    if(dp[r][0]!=-inf||dp[r][1]!=inf)return true;
    return false;
}

这个时候我们有了 n^3 做法：枚举所有区间然后判断

然后考虑如何优化这个东西

如果我们枚举区间左端点，尝试扩展到最远的右端点，然后统计答案是能写到 n^2 的

进一步，我们从大到小枚举左端点

考虑在更新过程中

要么在有限次操作内新的 \mathit{dp_{k,1,0}} 将与原来的相同，这时再往后将与原来完全一致，可以直接使用上次记录的最远点

要么在某个位置发现无法更新下去了，这个时候更新最远点即可

这貌似只是个常数优化？不，其实我们可以证明对于任意一个 f_{i} ，它最多被更新 7 次，所以这样就能切掉这个题了

下面是比较严谨的证明

在 i 之前找到一个最大的 j ，使得 a_{j} > a_{j+1} ，那么 a_{j} a_{j+1} 不能同时处于递增序列中， \mathit{dp_{i,0}} 必然为 a_j,a_{j+1} - \infty 中的一个

如果不存在这样的 j ，那么 \mathit{dp_{i,0}}= \infty

所以 \mathit{dp_{i,0}} 只有 4 种取值

同理，我们可以证明 \mathit{dp_{i,1}} 也只有四种取值

每次更新至少有一个值不同，一共 8 个取值，所以对于任意一个 f_i ，它最多被更新 7 次，复杂度是 O(n) 的

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int inf=0x3f3f3f;
const int maxn=2e5+15;
int a[maxn],n,dp[maxn][2],last;
long long ans=0;
void work(int l){
    dp[l][0]=inf;dp[l][1]=-inf;
    for(int i=l+1;i<=n;++i){
        int w0=-inf,w1=inf;
        if(dp[i-1][0]!=-inf){
            if(a[i]>a[i-1])w0=max(w0,dp[i-1][0]);
            if(a[i]<dp[i-1][0])w1=min(w1,a[i-1]);
        }
        if(dp[i-1][1]!=inf){
            if(a[i]<a[i-1])w1=min(w1,dp[i-1][1]);
            if(a[i]>dp[i-1][1])w0=max(w0,a[i-1]);
        }
        if(dp[i][1]==w1&&dp[i][0]==w0)break;
        else{dp[i][1]=w1;dp[i][0]=w0;}
        if(dp[i][0]==-inf&&dp[i][1]==inf){last=i-1;break;}
    }
    ans+=last-l+1;
}
int main(){
    scanf("%d",&n);last=n;
    for(int i=1;i<=n;++i)scanf("%d",&a[i]);
    for(int i=n;i>=1;--i)work(i);
    printf("%lld\n",ans);
    return 0;
}