专栏首页AI那点小事算法训练 K好数

算法训练 K好数

问题描述 如果一个自然数N的K进制表示中任意的相邻的两位都不是相邻的数字,那么我们就说这个数是K好数。求L位K进制数中K好数的数目。例如K = 4,L = 2的时候,所有K好数为11、13、20、22、30、31、33 共7个。由于这个数目很大,请你输出它对1000000007取模后的值。

输入格式 输入包含两个正整数,K和L。

输出格式 输出一个整数,表示答案对1000000007取模后的值。 样例输入 4 2 样例输出 7 数据规模与约定 对于30%的数据,KL <= 106;

对于50%的数据,K <= 16, L <= 10;

对于100%的数据,1 <= K,L <= 100。


AC代码如下(思路在注释里):

import java.util.Scanner;

public class Main {
    static int[][] dp;
    /*
     * dp[i][j]代表i位数中以j为首的k好数的个数
     * dp[i][0]全为1
     * 一般的j,p, 当p != j-1 && p != j+1
     * 那么dp[i][j] += dp[i-1][p]
     * 即i位数中以j为首的k好数的个数等于i-1位数中以不与j相邻的数为首的k好数的个数的和
     */
    static long MOD = 1000000007;

    public static void main(String[] args) {
        // TODO Auto-generated method stub
        Scanner in = new Scanner(System.in);
        int k = in.nextInt();
        int l = in.nextInt();
        int sum = 0;
        dp = new int[l][k];
        for ( int i = 1 ; i < k ; i++){
            dp[0][i] = 1;
        }

        for ( int i = 1 ; i < l ; i++){
            for ( int j = 0 ; j < k ; j++){
                for ( int p = 0 ; p < k ; p++){
                    if ( p != j-1 && p != j+1){
                        dp[i][j] += dp[i-1][p];
                        dp[i][j] %= MOD;
                    }
                }
            }
        }

        for ( int i = 0 ; i < k ; i++){
            sum += dp[l-1][i];
            sum %= MOD;
        }
        System.out.print(sum);
        in.close();
    }

}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 2016年腾讯笔试题——构造回文

    给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

    AI那点小事
  • 构造回文

    给定一个字符串s,你可以从中删除一些字符,使得剩下的串是一个回文串。如何删除才能使得回文串最长呢? 输出需要删除的字符个数。

    AI那点小事
  • 最长公共连续子串

    牛牛有两个字符串(可能包含空格),牛牛想找出其中最长的公共连续子串,希望你能帮助他,并输出其长度。 输入描述: 输入为两行字符串(可能包含空格),长度...

    AI那点小事
  • LCS(最长公共子序列问题)

    取出序列中某些特定的项并保持它们在原来序列中的顺序,所得到的新序列成为原序列的子序列。

    种花家的奋斗兔
  • 利用动态规划求解旅行商问题时空复杂度分析以及相关实验验证

    利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问...

    用户1621951
  • 转载 | 利用动态规划求解旅行商问题(Travelling Salesman Problem)时空复杂度分析以及相关实验验证

    利用动态规划求解旅行商问题(Travelling Salesman Problem,简称TSP)在之前的推文中已经有了详细的介绍,今天我们要对这个问题进行更深一...

    短短的路走走停停
  • 【HDU - 4345 】Permutation(DP)

    1到n的排列,经过几次置换(也是一个排列)回到原来的排列,就是循环了。 现在给n(<=1000),求循环周期的所有可能数。

    饶文津
  • 51Nod-1835-完全图

    ACM模版 描述 ? 题解 最近懒了好多,写题少了好多,闲来无事水一发…… DPDP 问题,设 dp[i][j]dp[i][j] 表示前 ii 个点形成 jj ...

    f_zyj
  • 状态压缩DP(大佬写的很好,转来看)

    奉上大佬博客 https://blog.csdn.net/accry/article/details/6607703 动态规划本来就很抽象,状态的设定和状态的...

    风骨散人Chiam
  • 浙江工业大学校赛 小M和天平

    小M和天平 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Ja...

    ShenduCC

扫码关注云+社区

领取腾讯云代金券