AOJ 2199 - Differential Pulse Code Modulation
Differential Pulse Code Modulation
提出コード
差の二乗を最小化したいので、動的計画法を利用します。
とし、入力信号の番目を見るとき、複合化後の出力信号の値がになるような遷移の中で、求めたい値の最小値を記録します。dpの配列は大きな値で初期化しておきます。
すると、
となります。
複合化後の信号の初期値は128であること、0未満になると0になること、255以上になると255になること、の3パターンの遷移のみ少し特殊になるので注意しましょう。
答えは、dp[n][j]の中の最小値になります。