ABC165 問題C [asarenメモ] #深さ優先
問題文にある階段状に増加する数列の全パターンの生成数は
N+M-1 Combination N 通り で最大見積もりは 19 C 10 = 92738 通り
なので全生成してからスコア計算で対応可能。
全生成の方法は深さ優先探索(DFS)で生成可能。以下pythonでの回答例。
N,M,Q = map(int,input().split(' '))
ret = 0
question = []
for _ in range(Q):
t = list(map(int,input().split(' ')))
question.append(t)
def score(A):
ans = 0
for q in question:
if (A[q[1]] - A[q[0]] == q[2]):
ans += q[3]
return ans
def dfs(A):
tail = A[-1]
if len(A) > N:
global ret
cur = score(A)
ret = max(ret, cur)
return
for i in range(M-tail+1):
dfs(A+[tail+i])
dfs([1])
print(ret)
意外にはまったのが ret変数を関数内でglobal宣言するところ。。まだ甘い。。 しかしこの回のCは難しかった。。
