DP F - NISHIO Hirokazu's Scrapbox (Auto-translated from Japanese)

DP F

DP_F

I did np.zeros where I made a two-dimensional array filled with zeros, but in raw Python it's TLE, so I made a raw list and then PyPy'd it.

chr is doing this to change the characters back to a string since they are integer values when buffer.read is done.

code:python

def solve(S, T):

sizeS = len(S)

sizeT = len(T)

m = [0 * (sizeT + 1) for _i in range(sizeS + 1)]

for i in range(1, sizeS + 1):

for j in range(1, sizeT + 1):

mij = max(

mi - 1j,

mij - 1,

mi - 1j - 1 + 1 if Si - 1 == Tj - 1 else 0

)

result = []

i = sizeS

j = sizeT

while i > 0 and j > 0:

if mij == mi - 1j:

i -= 1

elif mij == mij - 1:

j -= 1

else:

result.append(chr(Si - 1))

i -= 1

j -= 1

print("".join(reversed(result)))

---

This page is auto-translated from /nishio/DP F. If you looks something interesting but the auto-translated English is not good enough to understand it, feel free to let me know at @nishio_en. I'm very happy to spread my thought to non-Japanese readers.