2199-Differential Pulse Code Modulation

http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=2199&lang=jp
考え方
k番目の要素以降による二乗和はk番目以前の二乗和に対し独立なので、メモ化再起を行なう。
計算量はO(NM)
実装(C++)

#include <algorithm>
#include <vector>
#include <iostream>
#include <cstring>
using namespace std;

vector<int> codebook;
vector<int> x;
int n,m,memo[256][20001];
int solve(int now,int k){
	int res=(1LL<<31)-1,next=0;
	if(memo[now][k]>=0)return memo[now][k];
	if(k<n){
		for(int i=0;i<m;i++){
			next=now+codebook[i];
			if(next>255)next=255;
			if(next<0)next=0;
			res=min(res,solve(next,k+1));
		}
	}else{
		res=0;
	}
	return memo[now][k]=((now-x[k])*(now-x[k])+res);
}

int main(){
	std::ios_base::sync_with_stdio();
	for(;cin>>n>>m;){
		if(n+m==0)break;
		codebook=vector<int>(m);
		x=vector<int>(n+1);
		for(int i=0;i<m;i++)cin>>codebook[i];
		x[0]=128;
		for(int i=0;i<n;i++)cin>>x[i+1];
		memset(memo,-1,sizeof(memo));
		cout<<solve(128,0)<<endl;
	}
	return 0;
}