白駿1309動物園-Nodejs

このポスターは白準1309号動物園のプールを描いている.質問リンク
コードはjavascriptで書かれています.

質問する

1.問題の説明

動物園には横2間、横N間の下のようなケージがあります.

ライオンをケージに閉じ込めるときは、横にも縦にも置けません.

2 xNアレイにライオンを配置する場合は、どのくらいのライオンがいるかを決定するプログラムを作成してください.

ライオンを1匹置かない場合も、1つの場合の数字で計算します.

2.入力

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

3.出力

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

に答える

この問題はi번째 행の配置状態に依存するため、DPによって解決することができる.

ろんり

例を挙げて詳しく説明します.Nが3であると仮定する

i-1번째 행問題にライオンが1匹も配置されていない場合、1つの場合の数字と仮定すると1になります.

[N = 0]「空」「左ライオン」「右ライオン」の3つのケースがあります.

[N = 1]には7つのケースがあります

N-1行目、すなわち1行目[N = 3]できれば、数量=3

1行は空です.これは、0行目について可能であれば個数を求めることができることを意味します.

Nが0の場合の数字は1です.

上の行は空なので、N行目については、可能な場合は「空」、「左ライオン」、「右ライオン」の3種類があります.

したがって、N−1動作が空の場合、可能な数は비어있을 때である.

N-1行目、すなわち1行目1*3 = 3가지できれば数量=4

1行は空ではありません.すなわち、「N-1の数字-上の行が空の数字」を考慮します.

N-1の数=D[2]=3

上記の動作が空の場合、数字=D[1]=1

上記の行為が空であるため、N行目については、可能な場合はそれぞれ2種類ある.(空白または対角線方向)

したがって、N−1行が空でない場合、可能な数は비어있지 않을 때である.

従って、Nが3の場合、総数は(3-1)*2 = 4가지種である.

3+4 = 717の場合

N-1行目、すなわち2行目[N = 4]できれば数量=9

2行が空であることは、最初の行について可能であれば、1つの数字を求めることができることを意味する.

Nが1の場合の数字は3です.

上の行は空なので、N行目については、可能な場合は「空」、「左ライオン」、「右ライオン」の3種類があります.

したがって、N−1動作が空の場合、可能な数字は3*3=9である.

N-1行目、すなわち2行目비어있을 때できれば数量=8

1行は空ではありません.すなわち、「N-1の数字-上の行が空の数字」を考慮します.

N-1の数=D[2]=7

上記の動作が空の場合、数字=D[1]=3

上記の行為が空であるため、N行目については、可能な場合はそれぞれ2種類ある.(空白または対角線方向)

したがって、N-1行が空でない場合、可能な数は(7-3)*2=8種類である.

したがって,Nが4の場合,総数は비어있지 않을 때種である.

てんかしき

上記の例では、ルールを見つけることができます.

てんかしき
D[N] = D[N-2] + D[N-1] * 2

完全なコード

const input = require('fs').readFileSync('/dev/stdin').toString();
const N = Number(input);
const dp = [1, 3].concat(new Array(N - 1).fill(0));

for (let i = 2; i <= N; i++) {
    dp[i] = (dp[i-2] + dp[i-1]*2) % 9901;
}

console.log(dp[N]);