首页 > 试题广场 >

还原

[编程题]还原

有一个含有 n 个数字的序列，每个数字的大小是不超过 200 的正整数，同时这个序列满足以下条件：

$a_1 \le a_2 \$
$a_n \le a_{n-1} (n > 2) \$
$a_i \le max(a_{i-1},a_{i+1}) \$

但是很不幸的是，在序列保存的过程中，有些数字丢失了，请你根据上述条件，计算可能有多少种不同的序列可以满足以上条件。

数据范围： $3 \le n \le 10^4 \$ ，序列中的数字满足 $0 \le val \le 200 \$ ，数字为 0 时表示丢失

输入第一行是一个n，表示这个序列的长度。

输入第二行有n个非负整数，中间用空格隔开，如果数字为0，说明这个数字丢失了，其他数字则都在1-200之间。

输出仅包含一个整数，即方案数对998244353取模的结果。

示例1

输入

3
2 0 1

第二个数要求大于等于第一个数，则第二个数大于等于 2，且根据第二个条件，必须大于等于最后一个数，则大于等于 1 ，根据第三个条件，必须小于等于左边和右边的数的最大值，则小于等于 2 ，大于等于 2 ，所以序列只可为 2  2 1

算法知识视频讲解

暂无题解

动态规划算法工程师京东 2019

上传者：小小

难度：

8条回答 122收藏 11933浏览

查看代码

扫一扫，把题目装进口袋