数位DP--P2657--Windy数 java实现

2021/7/31 20:06:23

本文主要是介绍数位DP--P2657--Windy数 java实现,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!

什么是数位DP

数位 DP 问题往往都是这样的题型,给定一个闭区间 [L,R],让你求这个区间中满足 某种条件 的数的总数。

(来自 OI-WIKI )

按照一般的方法,我们会遍历区间[L,R],对每个数字进行判断,是否符合题目要求.

但是这类题目的区间范围往往都比较大,单纯地遍历每一个数字,会超时.

这种情况下,使用数位DP的方式,进行求解.

下面根据

进行具体分析

这类算法,基本都是套模板.所以也按照这道题目,将模板写出来.

题目背景

windy 定义了一种 windy 数。

题目描述

不含前导零且相邻两个数字之差至少为 2 的正整数被称为 windy 数。windy 想知道,在 ab 之间,包括 ab ,总共有多少个 windy 数?

输入格式

输入只有一行两个整数,分别表示 ab

输出格式

输出一行一个整数表示答案。

对于全部的测试点,保证

\[1 \leq a \leq b \leq 2 \cdot 10^9 \]

总体思路

1.问题转化

对于区间中的问题,我们将它简化成只有一个边界的问题.类似于计算区间和.

对于在区间[L,R]上,计算满足某项条件的数字的个数result.

假设我们有函数F(x),表示在[0,x]区间上,满足条件的数字的个数.

那么result = F(R)-F(L-1);

2.具体求出F(x)

对于给定的输入M,在区间范围[0,M]中,我们按照每一位数字进行枚举(区别于遍历每一个数字),记录所有的情况---相邻数字的差至少为2.将结果记录到数组 A[]中.

  • 如何描述一类数字的状态:

    我们使用当前枚举的数字的i位,当前位的前一位具体是数字j来来记录此种情况下的满足题目条件的情况有多少种.

    A[i][j] = result;

    举例:

    A[3][4] 记录的是当前位置在第三位,并且前一位(第二位)数字是4的情况.

  • 如何写转移方程

    考虑一般情况.

    举例:

    对于数字(范围)12345.

    \[A[3][1] = \sum_{i=0}^{9}A[4][i]\\ 当且仅当 |i-前一位的数字| \leq 2 的时候 \]

    表示当前位置是第三位,前一个位置是1的数,能够组成满足题目要求的情况的总和

    等于

    当前位置是第四位,前一个位置是0~9,能够组成满足题目要求的情况的总和.

    另外,对于记录状态的重复使用:

    对于11???,可以使用数组A[2][1]表示.

    对于10???,可以使用数组A[2][1]表示.

    它们都表示当前位置在第二位,前面一位是1的状态.所以只要计算过一次后,后面再次到这个状态,就能够直接使用了.

  • 特殊情况

    1. 对于前面数字位已经在边界的数字,需要单独计算,不能够使用之前表示的状态.

      仍旧以12345举例.

      对于状态A[3][2],表示当前位置是3,前面位置的状态是2的情况,

      表示的数字是12???.

      (10???,11??? 因为第二为取得了0或者1,所以后面的数字仍旧能够取0~9,所以不算边界)

      这种情况下,就不能使用跟之前类似的公式:

      \[A[3][1] = \sum_{i=0}^{9}A[4][i]\\ 当且仅当 |i-前一位的数字| \leq 2 的时候 \]

      因为第三位只能够取0~3三位, 如果取4~9,最终的数字会超出范围.

      所以,这部分单独处理.

      因为只有前面全部都取到了数字的边界,才会出现这种情况,所以增加对于状态的记录,记作limit

    2. 引入"前导零"状态,表示当前位置之前的所有数字全部是零.

      因为我们在枚举数字每一位的时候,会碰到例如这样的情况:

      00123.实际上代表数字123.但是我们不能因为第二位和第三位之间相差一,就否定这种情况.

      所以增加 "前导零" 状态, 记作lead .表示当前位置之前的所有位置,全部都是0.这种状态下,当前位置的数字可以没有顾及地从0取值到9.

    具体代码

    可以再对照着注释部分,理解代码.

    import java.io.BufferedReader;
    import java.io.InputStreamReader;
    import java.util.Arrays;
    import java.util.StringTokenizer;
    
    public class Main {
        static long[][] dp;
        static int[] positionNum;
        public static void main(String[] args) throws Exception {
            BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
            StringTokenizer st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int aa = Math.min(a,b);
            int bb = Math.max(a,b);
            //因为问的是闭区间,所以对于[L,R],需要的结果是F(R)和F(L-1).
            long aResult = getCnt(aa-1);
            long bResult = getCnt(bb);
            System.out.println(bResult-aResult);
        }
    
        private static long getCnt(int num){
            positionNum = new int[11];//这里记录数字地每一位,到数组positionNum中
            int index = 0;
            while (num>0){
                positionNum[index++] = num%10;
                num /= 10;
            }
            //因为给定数字的范围最大不超过2亿,所以数字位数不超过9位,这里第一维度使用了11
            //因为第二维代表数字的取值范围,所以最多就是0~9,一共10位.
            dp = new long[11][10];
            //将dp数组初始化为-1.因为后续需要记忆化搜索,通过初始化的-1,来表示,某个状态没有被记录到
            for(int i = 0;i<dp.length;i++){
                Arrays.fill(dp[i],-1);
            }
            return dfs(index-1,0,true,true);
        }
    	//通过dfs,进行动态规划过程.
        //position:当前数字是第几位,对应于A[i][j]中的i
        //preNum:当前位置的前一位是哪个数字,对应于A[i][j]中的j
        //isLimit:当前位置之前的所有数字位置,是否填入了它们能够达到的最大值
        //lead:前导零.当前位置之前所有位置,是否都为零.
        private static long dfs(int position, int preNum, boolean isLimit,boolean lead) {
            //如果搜索到了-1,说明每一位都被搜索到了,dfs可以在这里结束.
            if(position < 0){
                return 1;
            }
            //用于记录结果
            long result = 0;
            //记忆化的步骤.
            //1.如果前面位置填写的数字,没有达到最大值
            //2.dp[position][preNum]这个状态之前有过记录
            //3.前面数字全部都不是零
            //这种状态说明之前dfs时,已经计算过,这里直接使用.
            if(!isLimit && dp[position][preNum]!=-1 && !lead){
                return dp[position][preNum];
            }
            //如果position位置之前的所有数字都为它们位置的最大值,
            //那么当前位置最大只能够是读取的数字的当前位置的值
            //否则,这一位能够填写0~9,因为这种情况下不管怎么填写,数字都不会超过给定范围.
            int maxNum = isLimit?positionNum[position]:9;
            int abs;
            for(int i = 0;i<=maxNum;i++){
                abs = Math.abs(i-preNum);
                //条件:相邻两个数字之间的差值必须不小于2,并且是没有前导零的情况
                //如果有前导零,那么就不需要这个条件.
                if(abs<2 && !lead){
                    continue;
                }
                //下面进行的都是下一位的dfs.分类了不同情况,不同情况下,dfs的第三第四个参数不同
                //当前位置填写了最大的数字,并且前面的数字也填写成为了当前位置最大的数字
                if(i == maxNum && isLimit){
                    result += dfs(position-1,i,true,false);
                }
                //当前位置取值不是0或者没有前导零
                //1.如果没有前导零,无论当前位取值如何,该状态表示的数字都不会是当前位置之前全部是零的情况
                //2.如果当前位置取值非零,那么之后一定不是前导零的状态了
                else if(i != 0 || !lead){
                    result+= dfs(position-1,i,false,false);
                }
                //和上面的状态相反,这里就表示了,是前导零的状态.
                else{
                    result += dfs(position-1,i,false,true);
                }
            }
            //这里针对一般的情况,进行了结果记录,以便后续使用
            //一般情况的条件:
            //1.各个位置不是最大取值
            //2.不包含前导零状态
            if(!isLimit && !lead){
                dp[position][preNum] = result;
            }
            return result;
        }
    }
    
    


这篇关于数位DP--P2657--Windy数 java实现的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!


扫一扫关注最新编程教程