動物園

タイムアウトメモリコミット正解率2秒128 MB 2073610361813548.145%

質問する

ある動物園には横に2つ、横にNつのケージがあり、以下のようになっています.

この動物園にはライオンが住んでいて、ライオンをかごに閉じ込めたとき、横に縦に置くことはできません.この動物園のトナカイ師はライオンの安置問題に頭を悩ませている.
動物園のトナカイ師が頭を悩ませないように、2*N配列のライオンの数を知るプログラムを作成しましょう.ライオンが1匹も配置されていない場合でも、1つの場合の手段で打つことができます.

入力

第1行は我々のサイズN(1≦N≦100000)を与える.

しゅつりょく

1行目にライオンが置かれている場合は、残りの数字9901を出力します.

入力例1

4

サンプル出力1

41

コード#コード#

import java.io.*;

public class P_1309 {
    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][3];

        dp[1][0] = dp[1][1] = dp[1][2] = 1;
        for (int i = 2; i<= n; i++) {
            dp[i][0] = (dp[i - 1][0] + dp[i - 1][1] + dp[i - 1][2]) % 9901;
            dp[i][1] = (dp[i - 1][0] + dp[i - 1][2]) % 9901;
            dp[i][2] = (dp[i - 1][0] + dp[i - 1][1]) % 9901;
        }

        bw.write(Integer.toString((dp[n][0] + dp[n][1] + dp[n][2]) % 9901));
        bw.flush();
    }
}

コードの説明

この問題はdp問題である.
Brootforceで解くことができないのは、1マスあたり選択可能な数(1マス目にライオンを置くだけ)、(2マス目にライオンを置くだけ)、(ライオンを置かない)の3つの場合、縦の最低価格が100000に達すると3^100000になるので、質問の時間制限条件は2秒を超えています.
まず,dp[N]は2 xN格にライオンを置く場合と考えられる.
そう考えると、N番目の格子にライオンを置く方法は、前の格子N-1にライオンをどのように置くかの影響を受けます.
そこで2次元配列dp[i][j]で配列を修正した.
iはiの1段目を表し、
jは0、1、2が存在する場合、0はライオンを置かない数を示し、1は1番目の格にのみライオンを置く数を示し、2は2番目の格にのみライオンを置く数を示す.
i欄にライオンを2匹配置する場合は問題上限られているので、考えていません.
今考えてみれば、i号にライオンが全然入っていない場合、i-1号車でライオンはどこに置いても大丈夫です.
したがって、dp[i-1][0]+dp[i-1][1]+dp[i-1][2]はdp[i][0]の点火式となる.
最初の格子にライオンを入れるだけで、i-1の格子にも最初の格子にライオンを入れるだけなら避けられます.
i-1の2番目の格子にライオンやライオンが入っていないときは安全です.
したがって、dp[i−1][0]+dp[i−1][2]はdp[i][1]の点火式となる.
2番目の格子にライオンを入れるだけなら、i-1の格子にも2番目の格子にライオンを入れるだけなら大丈夫です.
i-1の1番目の格子にライオンやライオンが入っていないときは安全です.
したがって、dp[i−1][0]+dp[i−1][1]はdp[i][2]の点火式となる.
dp[N][0]=dp[N−1][0]+dp[N−1][1]+dp[N−1][2]dp[N][0] = dp[N-1][0] + dp[N-1][1] + dp[N-1][2]dp[N][0]=dp[N−1][0]+dp[N−1][1]+dp[N−1][2]
dp[N][1]=dp[N−1][0]+dp[N−1][2]dp[N][1] = dp[N-1][0] + dp[N-1][2]dp[N][1]=dp[N−1][0]+dp[N−1][2]
dp[N][2]=dp[N−1][0]+dp[N−1][1]dp[N][2] = dp[N-1][0] + dp[N-1][1]dp[N][2]=dp[N−1][0]+dp[N−1][1]
そして、最終的にはN行目にライオンが置かれている全ての場合、dp[N][0]、dp[N][1]、dp[N][2]を加算すればよい.
また、dp[1]の要素はすべて1に初期化されていることに注意してください.
指定したテーブルの最初のローのみを表示します.前のローがないため、前述した3つのケースがあります.
(1番目の格子にのみライオンを置く)、(2番目の格子にのみライオンを置く)、(ライオンを置かない)
従って、各配列要素dp[1][1]、dp[1][2]、dp[1][0]を1に初期化して開始する.