接龙数列问题的动态规划解法

接龙数列问题的动态规划解法

引用

CSDN

1.

https://m.blog.csdn.net/weixin_67289517/article/details/144309288

对于一个长度为 $K$ 的整数数列：$A_1, A_2, ..., A_K$，我们称之为接龙数列当且仅当 $A_i$ 的首位数字恰好等于 $A_{i-1}$ 的末位数字 $(2 \leq i \leq K)$。
例如 $12, 23, 35, 56, 61, 11$ 是接龙数列；$12, 23, 34, 56$ 不是接龙数列，因为 $56$ 的首位数字不等于 $34$ 的末位数字。
所有长度为 $1$ 的整数数列都是接龙数列。
现在给定一个长度为 $N$ 的数列 $A_1, A_2, ..., A_N$，请你计算最少从中删除多少个数，可以使剩下的序列是接龙序列？

输入格式

第一行包含一个整数 $N$。
第二行包含 $N$ 个整数 $A_1, A_2, ..., A_N$。

输出格式

一个整数代表答案。

数据范围

对于 $20%$ 的数据，$1 \leq N \leq 20$
对于 $50%$ 的数据，$1 \leq N \leq 10000$
对于 $100%$ 的数据，$1 \leq N \leq 10^5$，$1 \leq A_i \leq 10^9$。所有 $A_i$ 保证不包含前导 $0$。

输入样例：

5
11 121 22 12 2023

输出样例：

1

样例解释

删除 $22$，剩余 $11, 121, 12, 2023$ 是接龙数列。

思路

采用了背包思想，放与不放前提个数字的末位刚好与后一个数字首位相等我们可以选择放也可以选择不放，放则+1，不放则不变，当不等时只有一个选择那就是不放，由于会输入大量数据自定义了一个输入类，这是个死模板死记就行了，当数据量较大时，至少能比普通Scanner快两倍

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Arrays;

public class Main {
    static int n;
    static int[][] dp;
    static int[] arr;
    static class Scanner {
        StreamTokenizer streamTokenizer = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
        public int nextInt() throws IOException {
            streamTokenizer.nextToken();
            return (int) streamTokenizer.nval;
        }
    }
    public static void main(String[] args) throws IOException {
        Scanner sc = new Scanner();
        n = sc.nextInt();
        arr = new int[n];
        dp = new int[n + 1][20];
        for (int i = 0; i < n; i++) {
            arr[i] = sc.nextInt();
        }
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 0; j <= 11; j++) {
                if (j == 0) {
                    dp[i][j] = dp[i + 1][last(arr[i]) + 1] + 1;
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j]);
                }
                if (j != 0 && j == first(arr[i]) + 1) {
                    dp[i][j] = Math.max(dp[i + 1][last(arr[i]) + 1] + 1, dp[i][j]);
                    dp[i][j] = Math.max(dp[i + 1][j], dp[i][j]);
                }
                dp[i][j] = Math.max(dp[i + 1][j], dp[i][j]);
            }
        }
        System.out.println(n - dp[0][0]);
    }
    private static int first(int a) {
        int b = 0;
        while (a != 0) {
            b = a % 10;
            a /= 10;
        }
        return b;
    }
    private static int last(int a) {
        return a % 10;
    }
}