有一个含有 n 个数字的序列,每个数字的大小是不超过 200 的正整数,同时这个序列满足以下条件:
但是很不幸的是,在序列保存的过程中,有些数字丢失了,请你根据上述条件,计算可能有多少种不同的序列可以满足以上条件。
数据范围:
, 序列中的数字满足
, 数字为 0 时表示丢失
输入第一行是一个n,表示这个序列的长度。
输入第二行有n个非负整数,中间用空格隔开,如果数字为0,说明这个数字丢失了,其他数字则都在1-200之间。
输出仅包含一个整数,即方案数对998244353取模的结果。
3 2 0 1
1
第二个数要求大于等于第一个数,则第二个数大于等于 2,且根据第二个条件,必须大于等于最后一个数,则大于等于 1 ,根据第三个条件,必须小于等于左边和右边的数的最大值,则小于等于 2 ,大于等于 2 ,所以序列只可为 2 2 1
import java.util.Scanner; public class Main{ public static void main(String[] args) { Scanner sc = new Scanner(System.in); long mod = 998244353; int N = sc.nextInt(); int[] arr = new int[N + 10]; for (int i = 1; i <= N; i++) { arr[i] = sc.nextInt(); } long[][][] res = new long[N + 10][210][3]; long[] s1 = new long[210]; long[] s2 = new long[210]; //初始化 for (int i = (arr[1] == 0 ? 1 : arr[1]); i <= (arr[1] == 0 ? 200 : arr[1]); i++) { for (int j = (arr[2] == 0 ? 1 : arr[2]); j <= (arr[2] == 0 ? 200 : arr[2]); j++) { if (i == j) res[2][j][1]++; else if (i < j) res[2][j][2]++; } } for (int j = 1; j <= 200; j++) { s1[j] = s1[j - 1] + res[2][j][0] + res[2][j][1] + res[2][j][2]; s2[j] = s2[j - 1] + res[2][j][0] + res[2][j][1]; } //更新结构 for (int i = 3; i <= N; i++) { for (int j = (arr[i] == 0 ? 1 : arr[i]); j <= (arr[i] == 0 ? 200 : arr[i]); j++) { res[i][j][0] = (s2[200] - s2[j]) % mod; res[i][j][1] = (res[i - 1][j][0] + res[i - 1][j][1] + res[i - 1][j][2]) % mod; res[i][j][2] = s1[j - 1] % mod; } for (int j = 1; j <= 200; j++) { s1[j] = s1[j - 1] + res[i][j][0] + res[i][j][1] + res[i][j][2]; s2[j] = s2[j - 1] + res[i][j][0] + res[i][j][1]; } } long ans = 0; for (int j = (arr[N] == 0 ? 1 : arr[N]); j <= (arr[N] == 0 ? 200 : arr[N]); j++) { ans = (ans + res[N][j][0] + res[N][j][1]) % mod; } System.out.println(ans); } }https://www.acwing.com/solution/acwing/content/1873/