题意：
给一个序列$a$，对于每一位$a[i]$，要求满足$a[i]<=a[i-1]$或者$a[i]<=a[i+1]$，如果$a[i]=-1$，则表示该位未知，问最多有多少种序列可以满足条件。
思路：
$dp[i][j][k]$表示第$i$位填充$j$的时候与前一位的关系是$k$。
$k=0$表示$a[i]>a[i-1]$，$k=1$表示$a[i]=a[i-1]$，$k=2$表示$a[i]<a[i-1]$。转移式为：
$dp[i][j][0]=sum_{k=1}^{j-1}{(dp[i-1][k][0]+dp[i-1][k][1]+dp[i-1][k][2])}$
$dp[i][j][1]=dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2]$
$dp[i][j][2]=sum_{k=j+1}^{200}{(dp[i-1][k][1]+dp[i-1][k][2])}$
$ans=sum_{j=1}^{200}{(dp[n][j][1]+dp[n][j][2])}$
代码：
1 //#include<bits/stdc++.h> 2 #include <set> 3 #include <map> 4 #include <stack> 5 #include <cmath> 6 #include <queue> 7 #include <cstdio> 8 #include <string> 9 #include <vector> 10 #include <cstring> 11 #include <iostream> 12 #include <algorithm> 13 14 #define ll long long 15 #define pll pair<ll,ll> 16 #define pii pair<int,int> 17 #define bug printf("********* ") 18 #define FIN freopen("input.txt","r",stdin); 19 #define FON freopen("output.txt","w+",stdout); 20 #define IO ios::sync_with_stdio(false),cin.tie(0) 21 #define ls root<<1 22 #define rs root<<1|1 23 #define pb push_back 24 25 using namespace std; 26 const int inf = 2e9 + 7; 27 const ll Inf = 1e18 + 7; 28 const int maxn = 1e5 + 5; 29 const ll mod = 998244353; 30 31 ll dp[maxn][201][3]; 32 int a[maxn]; 33 34 int main() 35 { 36 int n; 37 scanf("%d", &n); 38 for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); 39 if (a[1] == -1) { 40 for (int i = 1; i <= 200; ++i) dp[1][i][0] = 1; 41 } 42 else { 43 dp[1][a[1]][0] = 1; 44 } 45 for (int i = 2; i <= n; ++i) 46 { 47 ll tmp = 0;//大于 48 for (int j = 1; j <= 200; ++j) { 49 if (a[i] == -1 || a[i] == j) dp[i][j][0] = tmp; 50 else dp[i][j][0] = 0; 51 tmp += dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]; 52 tmp %= mod; 53 } 54 //等于 55 for (int j = 1; j <= 200; ++j) { 56 if (a[i] == -1 || a[i] == j) 57 dp[i][j][1] = (dp[i - 1][j][0] + dp[i - 1][j][1] + dp[i - 1][j][2]) % mod; 58 else dp[i][j][1] = 0; 59 } 60 tmp = 0;//小于 61 for (int j = 200; j >= 1; --j) { 62 if (a[i] == -1 || a[i] == j) dp[i][j][2] = tmp; 63 else dp[i][j][2] = 0; 64 tmp += dp[i - 1][j][1] + dp[i - 1][j][2]; 65 tmp %= mod; 66 } 67 } 68 ll ans = 0; 69 for (int i = 1; i <= 200; ++i) { 70 if (a[n] == -1 || a[n] == i) { 71 ans += dp[n][i][1] + dp[n][i][2]; 72 ans %= mod; 73 } 74 } 75 printf("%lld ", ans); 76 }