AOJ-2199 : Differential Pulse Code Modulation

Problem C: Differential Pulse Code Modulation

「 差分パルス符号変調 」という音声信号を圧縮する際に用いられる圧縮手法が問題になっています。
入力信号を指定されたコードブックを使って、元信号と複合化後の信号の差の二乗和の最小値を求める問題。

解法としては、動的計画法を使って、DPテーブルを計算する問題。
dp[ i番目のサンプル数 ][ ynの値 (信号の値) ] を元に計算していく。

最終的にDPテーブルのN番目のサンプル数の配列の最小値が答えになっているので、それを出力。

DPテーブルの値が初期値の時に加算処理を行ってしまうと、反転して最小値になってしまうため、
そのときは計算してはいけないので、if文で飛ばしています。

計算結果を0 ~ 255に丸めるのは、round255関数を作って対応。

//http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199

#include<iostream>
#include<map>
#include<vector>
#include<algorithm>
#include<cmath>
#include<climits>
#include<ctime>
#include<cstring>
#include<numeric>

#define ALL(v) (v).begin(),(v).end()
#define REP(i,p,n) for(int i=p;i<(int)(n);++i)
#define rep(i,n) REP(i,0,n)
#define dump(a) (cerr << #a << "=" << (a) << endl)
#define DUMP(list) cout << "{ "; for(auto nth : list){ cout << nth << " "; } cout << "}" << endl;

using namespace std;

const int MAX = INT_MAX;

int N,M;
int dp[20001][256];

vector<int> C;
vector<int> x;

int round255(int n)
{
	if(n > 255){ return 255; }
	else if(n < 0){ return 0;}
	else{ return n; }
}

int main()
{
	while(cin >> N >> M && N)
	{
		C.resize(M);
		x.resize(N);
		fill_n((int *)dp, sizeof(dp)/sizeof(int), MAX);

		rep(i,M){ cin >> C[i]; }
		rep(i,N){ cin >> x[i]; }

		dp[0][128] = 0;

		rep(i,N)
		{
			rep(j,256)
			{
				if(dp[i][j] == MAX){ continue; }	
				rep(k,M)
				{
					int yn = j + C[k];
					yn = round255(yn);
					int sum2 = (x[i] - yn)*(x[i] - yn);
					dp[i+1][yn] = min(dp[i+1][yn], dp[i][j]+sum2);
				}
			}
		}

		cout << *min_element(dp[N],dp[N]+256) << endl;
	}
	return 0;
}