题意：
n<=1e5
思路：卡内存
dp[i][j][k]表示当前第i个数字为j，第i-1个数字与第i个之间大小关系为k的方案数(a[i-1]<a[i],=,>)
转移时使用前缀和和后缀和加速
如此简单的DP居然没有写出来，还想复杂了……
1 #include<cstdio> 2 #include<cstring> 3 #include<string> 4 #include<cmath> 5 #include<iostream> 6 #include<algorithm> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<vector> 11 using namespace std; 12 typedef long long ll; 13 typedef unsigned int uint; 14 typedef unsigned long long ull; 15 typedef pair<int,int> PII; 16 typedef vector<int> VI; 17 #define fi first 18 #define se second 19 #define MP make_pair 20 #define N 100010 21 #define M 200 22 #define MOD 998244353 23 #define eps 1e-8 24 #define pi acos(-1) 25 26 ll dp[N][M+10][3],tmp; 27 int a[N]; 28 29 30 int main() 31 { 32 //freopen("D.in","r",stdin); 33 //freopen("D.out","w",stdout); 34 int n; 35 scanf("%d",&n); 36 for(int i=1;i<=n;i++) scanf("%d",&a[i]); 37 for(int i=1;i<=M;i++) 38 { 39 if(a[1]==-1||i==a[1]) dp[1][i][0]=1; 40 else dp[1][i][0]=0; 41 } 42 tmp=0; 43 for(int i=2;i<=n;i++) 44 { 45 for(int j=1;j<=M;j++) 46 { 47 if(a[i]==-1||j==a[i]) dp[i][j][1]=(dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%MOD; 48 else dp[i][j][1]=0; 49 } 50 51 tmp=0; 52 for(int j=1;j<=M;j++) 53 { 54 if(a[i]==-1||j==a[i]) dp[i][j][0]=tmp; 55 else dp[i][j][0]=0; 56 tmp=(tmp+dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%MOD; 57 } 58 59 tmp=0; 60 for(int j=M;j>=1;j--) 61 { 62 if(a[i]==-1||j==a[i]) dp[i][j][2]=tmp; 63 else dp[i][j][2]=0; 64 tmp=(tmp+dp[i-1][j][1]+dp[i-1][j][2])%MOD; 65 } 66 } 67 ll ans=0; 68 for(int i=1;i<=M;i++) ans=(ans+dp[n][i][1]+dp[n][i][2])%MOD; 69 printf("%lld ",ans); 70 return 0; 71 }