AOJ 2502 VOCAL ANDROID

qiita.com

続きです。

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2502

サンプルケース通ったのに、ダメだったパターン。解答見ても謎。間違ってるところがわからないです。

わかる方いましたらコメントしてください。僕が喜びます。

WAコード

N = int(input())
s, l, p = ([], [], [])

for i in range(N):
    ss, ll, pp = [int(j) for j in input().split()]
    s.append(ss); l.append(ll); p.append(pp)

M = int(input())
w = []
for i in range(M):
    w.append(int(input()))

"""
def rec(pos, end, m):
    if pos == N or end >= m:
        if end == m:
            return 0
        return -100000
    ans = rec(pos+1, end, m)
    for i in range(s[pos], l[pos]+1):
        ans = max(ans, rec(pos+1, end+i, m) + p[pos])
    return ans

for i in w:
    print(rec(0, 0, i))

# rec2
def rec(pos, m):
    if pos == N or m <= 0:
        if m == 0:
            return 0
        return -100000
    # 入れないパターン
    ans = rec(pos+1, m)
    # 入れるパターン
    for i in range(s[pos], l[pos]+1):
        ans = max(ans, rec(pos+1, m-i) + p[pos])
    return ans

for i in w:
    print(rec(0, i))
"""

dp = [[0 for j in range(400+1)] for i in range(N+1)]

for i in range(N-1, -1, -1):
    for j in range(0, 400):
        dp[i][j] = dp[i+1][j]
        for k in range(s[i], l[i]+1):
            if j-k >= 0:
                dp[i][j] = max(dp[i][j], dp[i+1][j-k] + p[i])

for i in w:
    if dp[0][i] == 0:
        print(-1)
        break
else:
    for i in w:
        print(dp[0][i])

次は、他の人のACコード真似たやつです。pythonだとTLEですけどw

dp = [0 for i in range(400)]

n = int(input())

for i in range(1, n+1):
    s, l, p = map(int, input().split())
    for j in range(1, 400):
        for k in range(s, l+1):
            if j-k >= 0:
                dp[j] = max(dp[j], dp[j-k]+p)


m = int(input())
ws = []
for i in range(m):
    w = int(input())
    if dp[w] == 0:
        print(-1)
        break
    ws.append(w)

else:
    for w in ws:
        print(dp[w])

これは、1 次元dpでできるんだなという知見を得ました。

追記:

復習目的として、1次元にしたら無事TLEになったので、そういう問題なんだなという認識を得ました。

n = int(input())
s, l, p = ([], [], [])
for i in range(n):
    ss, ll, pp = map(int, input().split())
    s.append(ss); l.append(ll); p.append(pp)

"""
def rec(pos, v):
    if pos==n or v <= 0:
        if v == 0:
            return 0
        return -10000
    ans = rec(pos+1, v)
    for i in range(s[pos], l[pos]+1):
        if not v-i < 0:
            ans = max(ans, rec(pos+1, v-i)+p[pos])
    return ans
"""
m = int(input())
w = []
for i in range(m):
    w.append(int(input()))

"""
for ww in w:
    print(rec(0, ww))
"""

dp = [0 for i in range(401)]

for i in range(n-1, -1, -1):
    for j in range(0, 400):
        for k in range(s[i], l[i]+1):
            if j-k >= 0:
                dp[j] = max(dp[j], dp[j-k]+p[i])

for ww in w:
    if dp[ww] == 0:
        print(-1)
        break
else:
    for ww in w:
        print(dp[ww])

ふむ。