JOI 2012 予選 D 暑い日々

千里の道も一歩から。えぬわいです。

qiita.com

続きです。

atcoder.jp

おっしゃあこい。

再帰関数を書いて、観察。 そして、漸化式を導くぜ。

最初に、選んだものを全部リストに詰めて、次の呼び出しに渡すパターン。 これは言わずもがな、DP化できない。

次に書いたのは、1 つ前に選んだものだけを記録していくスタイル。

これは、初め、引数をそのまま返すパターンにしてたけど、前回、前々回ぐらいで、引数を減らせるパターンを生かして、+abs(c[i]-v) の形にできた。

2 番目に思いついた再帰関数は、最初にINFを渡して、最初かどうか判定していた(i != 0の部分)が、観察すると、pos で条件分岐ができるなということに気づいた。それをそのままDPに持っていったら、無事通った。時間的に割とギリギリだった気がする。

前みたいにcppで書けば、全然早くなると思う。

d, n = map(int, input().split())
t = []
for i in range(d):
    t.append(int(input()))
a, b, c = ([], [], [])
for i in range(n):
    aa, bb, cc = map(int, input().split())
    a.append(aa); b.append(bb); c.append(cc)

"""
def rec(pos, k):
    if pos == d:
        tmp = 0
        for i in range(1, len(k)):
            tmp += abs(c[k[i]]-c[k[i-1]])
        return tmp
    ans = 0
    for i in range(n):
        if a[i] <= t[pos] <= b[i]:
            k.append(i)
            ans = max(ans, rec(pos+1, k))
            k.pop()
    return ans

# 回答出力
print(rec(0, []))

INF = 1000000

def rec(pos, v):
    if pos == d:
        return 0
    ans = 0
    for i in range(n):
        if a[i] <= t[pos] <= b[i]:
            if pos != 0:
                ans = max(ans, rec(pos+1, c[i])+abs(c[i]-v))
            else:
                ans = max(ans, rec(pos+1, c[i]))
    return ans

# 回答出力
print(rec(0, INF))

"""
dp = [[0 for j in range(100+1)] for i in range(d+1)]

for i in range(d-1, -1, -1):
    for j in range(0, 100+1):
        for k in range(n):
            if a[k] <= t[i] <= b[k]:
                if i != 0:
                    dp[i][j] = max(dp[i][j], dp[i+1][c[k]]+abs(c[k]-j))
                else:
                    dp[i][j] = max(dp[i][j], dp[i+1][c[k]])

print(dp[0][100])