shin3110
@shin3110

Are you sure you want to delete the question?

If your question is resolved, you may close it.

Leaving a resolved question undeleted may help others!

We hope you find it useful!

dpのリスト作成時の少しの差でAC,WAが変わる理由が知りたい

知りたいこと

dpを実装していたら、よくわからない違いで間違えました。間違った方のコードだと、どのようなことが起こるのでしょうか

AC

N = int(input())
n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

scr = 0
pop = [-10**8 for _ in range(n+1)]
pop[1] = 0

for i in range(1, n):
	pop[a[i-1]] = max(pop[a[i-1]], pop[i]+100)
	pop[b[i-1]] = max(pop[b[i-1]], pop[i]+150)

print(pop[n]) 

WA

n = int(input())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
s = len(a)
scr = 0
pop = [0 for _ in range(n+1)]

for i in range(1, n):
	pop[a[i-1]] = max(pop[a[i-1]], pop[i]+100)
	pop[b[i-1]] = max(pop[b[i-1]], pop[i]+150)

print(pop[n]) 

二つのコードの差

dp用のリストを作成する部分

pop = [-10**8 for _ in range(n+1)]
pop[1] = 0
pop = [0 for _ in range(n+1)]

上がACのもので、下がWAのものです。
pop[0] は、途中いじったりしたつもりはないので、これが変わることで何が変わるのか教えてほしいです。

0

1Answer

0 で埋めるか -10**8 で埋めるかの違いがあるので、負の値があったときに、
max(負の値, -10**8)負の値 になり、
max(負の値, 0)0 になるので、違う結果になるのでは?

0Like

Your answer might help someone💌