7K12 blog

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

2020-05-26から1日間の記事一覧

ABC143 E - Travel by Car

https://atcoder.jp/contests/abc143/submissions/12257779 ワーシャルフロイド法を使ってショートカットを追加 補給回数の新しいグラフを作る 任意の頂点で燃料を満タンにリセットするため、単純な最短距離が最善とはならない。ワーシャルフロイド法を使う…

Kyoto University Programming Contest 2019 B - ナップサック問題

https://atcoder.jp/contests/kupc2019/submissions/13604182 初期値は dp[0]=0 繰り返しは rep(i, 1, Size(newItem)) rep(j, 0, n * Pow10(4) + 1) 更新は if (0 <= j - newItem[i].first) dp[i][j] = max({ dp[i][j], dp[i - 1][j], dp[i - 1][j - newItem…