yoshiki_utakata https://blog.hatena.ne.jp/yoshiki_utakata/ 猫でもわかるWeb開発・プログラミング https://www.utakata.work/ はじめに 問題: http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199 ソースコード: http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=1362790 Javaで実装 すごく良い問題だと思います 方針 問題文にあるように、貪欲法では解けないので、探索をすることになる。 しかし、全探索すると最悪で162000となってしまい間に合わない。 そこで動的計画法を使う。この問題においては、「今何番目か」「今の値はいくらか」という状態のなかで「最小二乗誤差の和」を最小にすればいい… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fwww.utakata.work%2Fentry%2F2015%2F05%2F23%2F104921" title="AOJ 2199: 差分パルス符号変調 (Differential Pulse Code Modulation) - 猫でもわかるWeb開発・プログラミング" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2015-05-23 10:49:21 rich https://www.utakata.work/entry/2015/05/23/104921 1.0 100%