AOJ 2199 - Differential Pulse Code Modulation

・問題
Differential Pulse Code Modulation | Aizu Online Judge

元の数列x(size<=10000)を、コードブックC(size<=16)を使って標本化する。
y_0=128から始めて、y_1=y_0+C[k_1], ... , y_n=y_n-1+C[k_n]という容量で数列yを決定する。この過程で、yの値が0未満になるときは0、255より大きくなるときは255にyの値をその都度丸める。
そのとき元の数列xとの差の二乗の和(y1-x1)^2+...+(yn-xn)^2の最小値を求めよ。

・アイデア
この問題は春休みぐらいにも一回やろうとしてわからずに挫折した。
ほんの少しだけDP力がついたおかげか、メモ化再帰的に書き上げることができた。やはり、どのように状態をもたせるかに一番苦心した。
状態を考えた時に、現在の数列の位置とその手前のyの値が同じならその後の計算が同じになることは漸化式が2項関係にあることを考えれば何となく分かる。
コードブックのサイズが16と非常に小さいので、1つの再帰に対しての操作はかなり軽い。
やっぱり試行錯誤しながらでもなんとか書いてみるのが上達の道なんだな...

・実装(C++)

#include <algorithm>
#include <climits>
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;

int n,m;
int c[16],x[20000];

long dp[20001][256];

long rec(int p, int y){ //現在p番目に注目しており、その手前の値はy。x[n]との差の二乗を返す
	if(dp[p][y]>=0) return dp[p][y];
	
	//終条件
	if(p==n) return 0;
	
	long ret=LONG_MAX;
	for(int i=0; i<m; ++i){ //コードブックの値全てに対して再帰をかける
		//次のyの値(丸めが発生することを考慮)
		int ny = y+c[i];
		if(ny<0) ny=0;
		else if(ny>255) ny=255;
		
		//コードブックの選んだ値の中で、二乗和が最小になるよう選ぶ
		ret = min(ret, rec(p+1,ny)+(ny-x[p])*(ny-x[p]));
	}
	
	return dp[p][y]=ret;
}

int main(){
	while(1){		
		//input
		scanf(" %d %d", &n, &m);
		if(n==0) break;
		for(int i=0; i<m; ++i) scanf(" %d", &c[i]);
		for(int i=0; i<n; ++i) scanf(" %d", &x[i]);	
		//solve
		memset(dp,-1,sizeof(dp));
		//最初はy_0=128
		printf("%ld\n", rec(0,128));
	}
}