排列游戏 --- 动态规划 --- 题解

目录

排列游戏

题目描述

输入描述:

输出描述:

输入

输出

备注:

思路：

代码：

---

?

排列游戏

K-排列游戏_牛客竞赛动态规划专题班习题课 (nowcoder.com)

时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld

题目描述

你拿到了一个神秘的字符串，这个字符串的长度为n，里面只有0,1,2三种数。但是你意识到了事情并不简单，这个字符串实际上隐藏的是一个长度为n+1的排列。我们将字符串和排列的下标从1开始标号，如果s[i]=1，那么说明排列aaa的第i位ai小于ai+1；如果s[i]=2，那么说明ai大于ai+1；如果s[i]=0，那么说明ai和ai+1?的关系任意。
现在你需要求出有多少种不同的排列满足条件，输出在模998244353意义下的答案。

（排列指的是 1 .... n 都出现了，并且只出现了一次）

输入描述:

一行一个字符串S。

输出描述:

输出一个整数表示在模998244353意义下的答案。

示例1

输入

102

输出

6

备注:

1≤n≤5e3

思路：

dp[i][j] 表示前i位满足要求，并且末尾小于等于j时的方案数。（边求解并统计前缀和）

由于求得是(1到n+1的排列，所以不能有重复数字)。则我们要求前i位只能填1-i这些数字，那么第i+1位填了1-i的数字j怎么解决，那么就让前i位大于等于j的数字加1，这样还是保证了i+1位中没有重复数字，并且也满足了题目的需求。

转移方程为
? ? ? ? ? ?当前位为?2? ? dp[i % 2][j] = (dp[(i - 1) % 2][i - 1] - dp[(i - 1) % 2][j - 1] + mod)% mod;
? ? ? ? ? ?当前位为?1? ?dp[i % 2][j] = dp[(i - 1) % 2][j - 1] % mod;?
? ? ? ? ? ?当前位为 0? ?dp[i % 2][j] = dp[(i - 1) % 2][i - 1] % mod;

代码：

import java.io.*;
import java.math.BigInteger;
import java.util.StringTokenizer;

/**
 * @ProjectName: study3
 * @FileName: Ex8
 * @author:HWJ
 * @Data: 2023/12/8 10:59
 */
public class Main {
    public static void main(String[] args) {
        String str = input.next();
        int mod = 998244353;
        char[] s = str.toCharArray();
        int n = s.length;
        int[][] dp = new int[2][n + 2];
        dp[1][1] = 1;
        for (int i = 2; i <= n + 1; i++) {
            for (int j = 1; j <= i; j++) {
                dp[i % 2][j] = 0;
                if (s[i - 2] == '2') {
                    dp[i % 2][j] = (dp[(i - 1) % 2][i - 1] - dp[(i - 1) % 2][j - 1] + mod)% mod;
                } else if (s[i - 2] == '1') {
                    dp[i % 2][j] = dp[(i - 1) % 2][j - 1] % mod;
                } else {
                    dp[i % 2][j] = dp[(i - 1) % 2][i - 1] % mod;
                }
            }
            for (int j = 1; j <= i; j++) {
                dp[i % 2][j] = (dp[i % 2][j - 1] + dp[i % 2][j]) % mod;
            }
        }
        out.println(dp[(n + 1) % 2][n + 1]);
        out.flush();
        out.close();
    }

    static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
    static Input input = new Input(System.in);
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

    static class Input {
        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public Input(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream), 32768);
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            String str = null;
            try {
                str = reader.readLine();
            } catch (IOException e) {
                // TODO 自动生成的 catch 块
                e.printStackTrace();
            }
            return str;
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public Double nextDouble() {
            return Double.parseDouble(next());
        }

        public BigInteger nextBigInteger() {
            return new BigInteger(next());
        }
    }
}