11057上り坂水

タイムアウトメモリ制限回答を提出した人回答正解率1秒256 MB 37897184241420647.432%

質問する

上り坂数とは、数字の位置が昇順に並ぶ数です.このとき、隣接する数が同じでも昇順に打つ.
例えば、2234および367811119は上り坂であり、2232676911は上り坂ではない.
数の長さがNの場合、上り坂を求めるプログラムを作成してください.数はゼロから始まることができます.

入力

第1行はN(1≦N≦1000)を与える.

しゅつりょく

出力1行目の長さNの上り坂数を10007の残りの部分で割った.

入力例1

1

サンプル出力1

10

入力例2

2

サンプル出力2

55

入力例3

3

サンプル出力3

220

コード#コード#

import java.io.*;

public class P_11057 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        int n = Integer.parseInt(br.readLine());
        int[][] dp = new int[n + 1][10];

        for (int i = 0; i < 10; i++) dp[1][i] = 1;
        for (int i = 2; i<= n; i++) {
            for (int j = 0; j<= 9; j++) {
                for (int k = 0; k <= j; k++) dp[i][j] = (dp[i][j] + dp[i - 1][k]) % 10007;
            }
        }

        int sum = 0;
        for (int i = 0; i< 10; i++) sum = (sum + dp[n][i]) % 10007;

        bw.write(Integer.toString(sum));
        bw.flush();
    }
}

コードの説明

時間複雑度は1秒であり,Brootforceで解くと9^1000なので,1秒を超えるとdpで解く.
dp[n]はnビットの上り坂数の個数である.
このとき,n位上り坂数はn−1位上り坂数がどのように終わるかの影響を受ける.
n−1位上り坂数が0であれば、n位に0~9を入れてn位上り坂数を生成し、n−1位上り坂数が9であれば、n位に9を入れてn位上り坂数を生成する.
だからdpは2次元配列で、どんな数字で終わるかの情報が含まれています.
dp[i][j]は、i位上り坂数のうちjで終わる上り坂数の個数を表す.
このとき、jで終わる上り坂数は、i−1位上り坂数のうちj以下で終わる上り坂数に等しい.
だから点火式.
dp[i][j]=dp[i−1][1]+...+dp[i−1][j]dp[i][j] = dp[i - 1][1] + ... + dp[i - 1][j]dp[i][j]=dp[i−1][1]+...+dp[i−1][j]
いいですよ.