考虑三种情况，刷表dp+前缀和预处理即可
#include<bits/stdc++.h> using namespace std; const int mo=998244353; long long n,k,a[100005],f[2][205][3],ans,s; int main(){ scanf("%lld",&n); for(int i=1;i<=n;++i) scanf("%lld",a+i); if(a[1]==-1) for(int i=1;i<=200;++i) f[k][i][0]=1;else f[k][a[1]][0]=1; for(int i=2;i<=n;k^=1,++i){ s=0; for(int j=1;j<=200;++j){ f[k^1][j][0]=(a[i]==-1||a[i]==j)?s:0; (s+=f[k][j][0]+f[k][j][1]+f[k][j][2])%=mo; } for(int j=1;j<=200;++j) f[k^1][j][1]=(a[i]==-1||a[i]==j)?(f[k][j][0]+f[k][j][1]+f[k][j][2])%mo:0; s=0; for(int j=200;j;--j){ f[k^1][j][2]=(a[i]==-1||a[i]==j)?s:0; (s+=f[k][j][1]+f[k][j][2])%=mo; } } for(int i=1;i<=200;++i) (ans+=f[k][i][1]+f[k][i][2])%=mo; return !printf("%lld",ans); }
转载于:https://www.cnblogs.com/zsben991126/p/10931374.html
