おはやし日記

特にテーマ無しの日記。

DP

Codeforces 1373 D. Maximum Sum on Even Positions

こんにちは。こどふぉでした。 C、bit全探索でそれなりの数sを生成してもpseudocodeと自分のコードに差が出ないので原因不明だ— おはやし (@hys2490_tw) June 25, 2020 はい、もしやと思ってintを全部long longにしたら通りました気づくのが遅すぎる— おはや…

AtCoder ABC134 E - Sequence Decomposing を解く [C++]

こんにちは。今夜はABC169です。ここ数日競プロに触ってなかったので、やっとくか!ということで未解答だったABC134に挑戦しました。そしたらE問題が、先日勉強したDPの応用ですらっと解けて嬉しかったので書いています。 o-treetree.hatenablog.com こちら…

DP(動的計画法)でレーベンシュタイン距離(編集距離)問題を解くまでの過程メモ

昨日は最長増加部分列の問題を解きました https://o-treetree.hatenablog.com/entry/DPL1D 今日は、AOJの編集距離の問題を解きます。 といっても、相変わらずDPテーブルは思いつかなかったので検索してわかりやすかった解説を紹介する感じです。 参考にする…

DP(動的計画法)で最長増加部分列(LIS)問題を解くまでの過程メモ

なんか連載みたいになってんな 前回はDPでナップザック問題を解きました。 AOJでその次にあった最長増加部分列を解きました。 というか、解けなかったので検索して最長増加部分列(LIS)の長さを求める - Qiitaを見てなるほど〜ってなったのを自分なりにまとめ…

DP(動的計画法)でナップザック問題を解くまでの過程メモ

0-1 ナップザック問題 この0-1ナップザック問題が解けたので動的計画法初心者がその思考過程を記録しておく。 その後、簡単な書き換えによって一般ナップザック問題(命名: おはやし)が解けたので追記している。 先にコイン問題 前段階としてコイン問題(何…

DP(動的計画法)でコイン問題を解くまでの過程メモ

これは、https://o-treetree.hatenablog.com/entry/DPL1B(明日投稿)の前段階の記事です。動的計画法(どうてきけいかくほう、英: Dynamic Programming, DP)で「コイン問題」を解いていますが、DPとはなんぞや、みたいなところには触れておらず、解説を見…

プライバシーポリシー ・お問い合わせはこちら