Day 8.
This problem requires knowledge of dynamic programming.
This type of DP is called Ear DP because its algorithm appeared in the problem whose name is "Ears".
Ear DP requires current position and situation. (situation is sometimes n length arrays)
Code is below.
N = int(input())
S = str(input())
target = "atcoder"
dp = [[0]*(len(target)+1) for _ in range(N+1)]
dp[0][0] = 1
for i in range(N):
for j in range(len(target)):
if S[i] == target[j]:
dp[i+1][j+1] += dp[i][j]
dp[i+1][j] += dp[i][j]
dp[i+1][len(target)] += dp[i][len(target)]
MOD = 10**9 + 7
print(dp[N][len(target)]%MOD)
- もとの問題、Earsはこちら。
- ついでなので、こちらも書いてみる。
L = int(input())
#4で割った余りが1か3なら、1に圧縮、2か0なら2に圧縮。
#ただし、本当に0なら、そのまま0。
#すると、0，1，2の配列になる。
def Score(a,j):
if j == 0:
return a
#糸がない時は、そのまま足される
elif j == 1:
return abs(a%2 - 1)
#糸が1本なら、偶数は1，奇数なら0を返す
else:
#糸が2本の時を考える
if a == 0:
return 2
#スコアがないなら、2を返す
else:
return abs(a%2)
#偶数は0、奇数は1を返す
def Candidate(num):
if num == 0:
return [0,1,2]
#糸がない状況から、0,1,2本の状況はあり得る
elif num == 1:
return [1,3,5]
#糸が1本の状況から、1,二度目の0、二度目の2本
elif num == 2:
return [1,2,3]
#糸が2本の状況から、1,2，二度目の0本
elif num == 3:
return [3]
#糸が二度目の0本から、二度目の0本
elif num == 4:
return []
else:
return [3,5]
#糸が二度目の2本から、二度目の0，二度目の2本
INF = 10**9
dp = [ [INF for i in range(6)] for j in range(L+1)]
dp[0][0] = 0
#dpをしよう
for i in range(L):
a = int(input())
for j in range(6):
candidate = Candidate(j)
#今の後に、どんな糸の状態があり得るか
for k in candidate:
#候補の中から
score = Score(a,k%3)
#候補ごとの得点を調べる
dp[i+1][k] = min(dp[i][j]+score, dp[i+1][k])
#局所的に更新する
print(min(dp[L]))
- 耳DPは局所的な情報を抑えながら、局所の情報が順々に遷移していくので、 遷移していく法則を認識した上で、コードにお絵かきすれば、解決。
- 耳DPの気持ち
- 今回は、ボトムアップ（組み立てる方）を採用した。
- 以前、動的計画法として、出てきた問題でも桁ごとに、部分問題にして扱っていた。
medical-science.hatenablog.com
バイバイ！