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; }