CF1067A Array Without Local Maximums

常规dp题

题解：

设$f[i][j][0/1]$表示前$i$个数，第$i$个数选$j$，第$i-1$个数是否大于等于第$i$个数的方案数，显然的，1表示合法，0表示不合法

（注意：题目中有-1的条件，其实处理起来只需要把定值$a[i]$换成一层从1到200的循环枚举即可，下文中统一用$a[i]$替代）

初始化$f[1][a[i]][0]=1$

转移考虑分类讨论：

循环枚举第$i-1$个数为$k$，那么$j$与$k$会有三种大小关系：

  • j等于k

对$f[i][j][1]$造成影响，因为$j$对于$k$是合法的，前面一位只要选$k$就合法，所以$f[i][j][1]+=f[i-1][k][0]+f[i-1][k][1]$

  • j小于k

对$f[i][j][1]$造成影响，因为$j$对于$k$是不合法的，$k$的前一位对于$k$就一定要是合法的，所以$f[i][j][1]+=f[i-1][k][1]$

  • j大于k

对$f[i][j][0]$造成影响，因为$j$对于$k$是合法的，前面一位只要选$k$就合法，所以$f[i][j][0]+=f[i-1][k][0]+f[i-1][k][1]$

由此，可以得出如下dp代码：

for(int j=1;j<=200;j++){//当前位
    for(int k=1;k<=200;k++){//上一位 
        if(k==j) f[i][j][1]=(f[i][j][1]+f[i-1][k][0]+f[i-1][k][1])%mod;
        if(k>j) f[i][j][1]=(f[i][j][1]+f[i-1][k][1])%mod;
        if(k<j) f[i][j][0]=(f[i][j][0]+f[i-1][k][0]+f[i-1][k][1])%mod;
    } 
}

这样的dp是$O(200^2*n)$的，但不难看出这可以用前缀和优化

维护$f[i][j][0/1]$的前缀和，再合并一下dp方程，我们就可以$O(1)$算出$f[i][j][0/1]$，复杂度就降为$O(200*n)$

代码：

#include <bits/stdc++.h>
using namespace std;
template<class t> inline t read(t &x){
    x=0;char c=getchar();bool f=0;
    while(!isdigit(c)) f|=c=='-',c=getchar();
    while(isdigit(c)) x=(x<<1)+(x<<3)+(c^48),c=getchar();
    if(f) x=-x;return  x;
}
template<class t> inline void write(t x){
    if(x<0){putchar('-'),write(-x);}
    else{if(x>9)write(x/10);putchar('0'+x%10);}
}

#define int long long

const int mod=998244353;
const int N=1e5+5,M=205;
int n,a[N],f[N][M][2],ans,sum[M][2];

int calc(int l,int r,int op){
    return ((sum[r][op]-sum[l-1][op])%mod+mod)%mod;
}

signed main(){
    read(n);
    for(int i=1;i<=n;i++)
        read(a[i]);
    if(a[1]==-1) for(int i=1;i<=200;i++) f[1][i][0]=1;
    else f[1][a[1]][0]=1;
    for(int i=1;i<=200;i++){
        sum[i][0]=sum[i-1][0]+f[1][i][0];
        sum[i][1]=sum[i-1][1]+f[1][i][1];
    }
    for(int i=2;i<=n;i++){
        if(a[i]==-1){
            for(int j=1;j<=200;j++){
                f[i][j][1]=(calc(j,j,0)+calc(j,200,1))%mod;
                f[i][j][0]=(calc(1,j-1,0)+calc(1,j-1,1))%mod;
            }
        }
        else{
            f[i][a[i]][1]=(calc(a[i],a[i],0)+calc(a[i],200,1))%mod;
            f[i][a[i]][0]=(calc(1,a[i]-1,0)+calc(1,a[i]-1,1))%mod;
        }
        for(int j=1;j<=200;j++){
            sum[j][0]=sum[j-1][0]+f[i][j][0];
            sum[j][1]=sum[j-1][1]+f[i][j][1];
        }
    }
    if(a[n]==-1) for(int i=1;i<=200;i++) ans=(ans+f[n][i][1])%mod;
    else ans=f[n][a[n]][1];
    write(ans);
}
赏

fighter