ツバサの備忘録

主に備忘録代わりに精進記録を載せていくつもりです。

AOJ 2199 - Differential Pulse Code Modulation

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