JOI 2012 予選 D 暑い日々
千里の道も一歩から。えぬわいです。
続きです。
おっしゃあこい。
再帰関数を書いて、観察。 そして、漸化式を導くぜ。
最初に、選んだものを全部リストに詰めて、次の呼び出しに渡すパターン。 これは言わずもがな、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])