Codeforces Round #518 (Div. 2): D. Array Without Local Maximums（DP）

题意：

有一个长度为n的序列，满足对于所有的a[x]，与它相邻的两个元素a[x-1]和a[x+1]中至少有一个大于等于它，其中a[1]和a[n]当然只有一个相邻元素， 现在这个序列中有些数字被破坏了（标记为-1），问有多少种合法恢复方案（每个数字∈[1,200]）

思路：

dp[x][y][0/1/2]表示已经确定了第x个数字为y，且它左面那个数字a[x-1]小于/等于/大于它的总方案个数

#include<stdio.h>
#include<string.h>
#include<algorithm>
#include<map>
#include<string>
#include<math.h>
#include<queue>
#include<stack>
#include<iostream>
using namespace std;
#define LL long long
#define mod 998244353
LL dp[100005][205][3];		//0<  1=  2>
int a[100005];
int main(void)
{
	LL sum;
	int n, i, j;
	scanf("%d", &n);
	for(i=1;i<=n;i++)
		scanf("%d", &a[i]);
	for(i=1;i<=200;i++)
	{
		if(a[1]==-1 || a[1]==i)
			dp[1][i][0] = 1;
		else
			dp[1][i][0] = 0;
	}
	for(i=2;i<=n;i++)
	{
		for(j=1;j<=200;j++)
		{
			if(a[i]==-1 || a[i]==j)
				dp[i][j][1] = (dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%mod;
			else
				dp[i][j][1] = 0;
		}
		sum = 0;
		for(j=1;j<=200;j++)
		{
			if(a[i]==-1 || a[i]==j)
				dp[i][j][0] = sum;
			else
				dp[i][j][0] = 0;
			sum = (sum+dp[i-1][j][0]+dp[i-1][j][1]+dp[i-1][j][2])%mod;
		}
		sum = 0;
		for(j=200;j>=1;j--)
		{
			if(a[i]==-1 || a[i]==j)
				dp[i][j][2] = sum;
			else
				dp[i][j][2] = 0;
			sum = (sum+dp[i-1][j][1]+dp[i-1][j][2])%mod;
		}
	}
	sum = 0;
	for(i=1;i<=200;i++)
		sum = (sum+dp[n][i][1]+dp[n][i][2])%mod;
	printf("%lldn", sum);
	return 0;
}
/*
2
-1 -1
*/

最后

以上就是刻苦战斗机为你收集整理的Codeforces Round #518 (Div. 2): D. Array Without Local Maximums（DP）的全部内容，希望文章能够帮你解决Codeforces Round #518 (Div. 2): D. Array Without Local Maximums（DP）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。