7K12 blog

猫でも分かるアルゴリズム解説

2020-07-13から1日間の記事一覧

第14回日本情報オリンピック 本選 B - ケーキの切り分け2 (Cake 2)

https://atcoder.jp/contests/joi2015ho/submissions/15037441 https://atcoder.jp/contests/joi2015ho/submissions/15727225 循環バッファはサイズを余分に持つと実装がシンプルになる 区間DPは逆順に処理しても同値というテクニックが使える場合がある 初…

AOJ ALDS1_10_B Matrix Chain Multiplication

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4663385 行列の順番は変えずに「どの区間の行列から掛け算するのが最善か」という問題 初期値は rep(i, 0, n) dp[i][i] = 0; それ以外は inf 繰り返しは rep(range, 1, n) rep(l, 0, n) 更新は rep(m,…

DPL_1_B 0-1 Knapsack Problem

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4516218 初期値 dp[0][w] = 0; 繰り返しは rep(i, 1, Size(item)) rep(j, 0, W + 1) 更新は dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - item[i].second] + item[i].first }); 出力は dp…