cf div2 D dp

D. Array Without Local Maximums

题目链接

题意

给一个数组，给出一个数组，（1e5） 包含数字 1~200 或 -1 -1代表这个数字不知道是多少，让构造数组，把-1填上 ，使得数组里的每一位数字都有旁边的两个数至少有一个大于等于这个数。也就是 ai≤max(ai−1,ai+1)，问有多少种方法构造。

显然是dp 但是就是想不到怎么写，
大佬们都说这是很简单的dp。。。

题解
dp数组： dp[3][200][100005]
代表的意思：
3代表与前一位的关系，0 ： 小于前一位， 1 : 等于前一位， 2 : 大于前一位。
200 代表当前数字是多少，
后面那个100005 就是第i位了。
状态转移：
满足题目条件:
第 i 位为 j
等于i - 1的情况: dp[1][j][i] = (dp[0][j][i - 1] + dp[1][j][i - 1] + dp[2][j][i - 1]) % mod;
小于i - 1的情况：在第i - 1位 因为第i位小于第 i - 1位 所以 第i - 1位只能小于等于第i - 2 位 不能大于 。 第j - 1 ~ n都满足。所以求后缀和。
大于 i - 1的情况 : 第i - 1 位任意 1~ j - 1位 所以求前缀和。
说的好乱。。
代码：

#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
const int maxn = 1e5+5;
const ll mod = 998244353;
int a[maxn];
ll dp[3][201][maxn];
// 0 xiaoyu 1 dengyu 2 dayu qianyige 



int main()
{
   
	int n;
	scanf("%d",&n);
	for (int i = 1; i <= n; i ++ )
	{
   
		scanf("%d",&a[i]);
	}
	for (int i = 1; i <= 200; i ++ )//这里要更新成大于前一个的 。。 为什么？ 因为要让第二个大于等于第一个数
	{
   
		if(a[1] == i || a[1] == -1)
			dp[2][i][1] = 1;
		else
			dp[2][i][1] = 0;
	}
	for (int i = 2; i <= n; i ++ )
	{
   
		for (int j = 1; j <= 200; j ++ )
		{
   
			if(a[i] == -1 || a[i] == j)
			{
   
				dp[1][j][i] = (dp[0][j][i - 1] + dp[1][j][i - 1] + dp[2][j][i - 1]) % mod;
			}
			else
				dp[1][j][i] = 0;
		}
		ll temp = 0;
		for (int j = 200; j >= 1; j -- )
		{
   
			if(a[i] == -1 || a[i] == j)
			{
   
				dp[0][j][i] = temp;
			}
			else
				dp[0][j][i] = 0;
			temp = (temp + dp[1][j][i - 1] + dp[0][j][i - 1] ) % mod;
		}
		temp = 0;
		for (int j = 1; j <= 200; j ++ )
		{
   
			if(a[i] == -1 || a[i] == j)
			{
   
				dp[2][j][i] = temp;
			}
			else
				dp[2][j][i] = 0;
			temp = (temp + dp[0][j][i - 1] + dp[1][j][i - 1] + dp[2][j][i - 1]) % mod;
		}
	}
	ll ans =0 ;
	for (int i = 1; i <= 200; i ++ )
	{
   
		ans = (ans + dp[1][i][n] + dp[0][i][n]) % mod;
		// printf("%lld %lld %lld\n",dp[0][i][n],dp[1][i][n],dp[2][i][n]);
	}
	printf("%lld\n",ans);
}