首页 > 试题广场 >

还原

[编程题]还原
  • 热度指数:2173 时间限制:C/C++ 1秒,其他语言2秒 空间限制:C/C++ 256M,其他语言512M
  • 算法知识视频讲解
有一个含有 个数字的序列,每个数字的大小是不超过 200 的正整数,同时这个序列满足以下条件:






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

数据范围:  , 序列中的数字满足  , 数字为 0 时表示丢失

输入描述:
输入第一行是一个n,表示这个序列的长度。

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


输出描述:
输出仅包含一个整数,即方案数对998244353取模的结果。
示例1

输入

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/
发表于 2020-04-16 23:23:56 回复(0)