2193号は手作りです.

8325 ワード
DP boj テキストリンク
質問元:https://www.acmicpc.net/problem/2193
動的計画法を用いて動的計画法の基礎問題を簡単に解決できる

草。


入力値をリストし、Nビットがどのように親水性個数を決定するかを観察し、問題の条件によって条件は以下のように変化する.
1. N자리에서 0으로 끝나는 이친수에 의해 N+1자리에서는 두 개의 이친수( 0으로 끝나는, 1로 끝나는 수)가 추가로 생성된다.]
2. N자리에서 1로 끝나는 이친수에 의해 N+1자리에서는 한 개의 이친수 ( 0으로 끝나는 수 )가 추가로 생성된다.
3. 모든 이친수는 10XXX...로 시작되어야 한다. ( 1자리수( =1) 제외 )
これに基づいて、N+1ビットのこの親水個数をNビットとして記憶するこの親水個数の動的計画法を完成させることができる.
import sys

N = int(sys.stdin.readline().rstrip("\n"))

pinary = [[0,0] for _ in range(N+1)]
pinary[1][0],pinary[1][1] = 0,1

for i in range(2,N+1) :
    pinary[i][0] = pinary[i-1][0]+pinary[i-1][1]
    pinary[i][1] = pinary[i-1][0]

print(pinary[N][0]+pinary[N][1])

草。


他の人の答えは時間の複雑さが私より少し速い.だからもっと早く終わるコードを探したいです.以前のような問題(01タイル)のように,実際には結果値だけで問題を解決できる.(これもDPです.DPかN位かという親水の個数はN-1、N-2位という親水の個数で決まるので…)
import sys

N = int(sys.stdin.readline().rstrip("\n"))

pinary=[0 for _ in range(N+1)]
pinary[1]=1
for n in range(2,N+1) :
    pinary[n]=pinary[n-1]+pinary[n-2]
print(pinary[N])
時間がかわいそうに少ない.

追加..。


友达が本当に短すぎてできない感じがするので参考にしたいです.
a=1
b=1
n=int(input())
for i in range(n-1):
   a,b=b,a+b
print(a)
これは何ですか...?ドアの中の線を初めて見たので、役を探さなければなりません.
答え:答えRE:見えないRecaptchaのuncatch型エラーは、フォーム提出します
golang+json-iterator(微信ウィジェットプッシュ通知例)