ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

AOJ 2199 Differential Pulse Code Modulation

問題文はこちら↓
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199


・解説
動的計画法(DP)で解く。(単純にやろうとするとTLEしてしまう)

dp[何番目のサンプルか≦ 20000][音声信号の値 ≦ 255] = 二乗和の最小値
になるように実装する。


・感想
最初問題を見た時にすぐDPだろうなぁーとは予測できたのですが、実装に詰まってしまいました。
そこで、nanikakaさんのブログを少しチラ見させていただきました。感謝です。
ちょっとDP力が上がったような気がします。


ソースコード

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

#define rep(i,n) for(int i = 0 ; i < (int)(n) ; i++)

int N,M;
int dp[20010][256], c[16], x[20010];
static const int INF = (1<<29);

int solve(){
   rep(i,N+1){
      rep(j,256){
	 dp[i][j] = INF;
      }
   }
   dp[0][128] = 0;

   rep(i,N){
      rep(j,256){
	 if(dp[i][j]==INF)continue;
	 rep(k,M){
	    int next = j + c[k];
	    if(next < 0)next = 0;
	    if(next > 255)next = 255;
	    dp[i+1][next] = min(dp[i+1][next], dp[i][j]+(x[i]-next)*(x[i]-next));
	 }
      }
   }

   int ans = INF;
   rep(j,256)ans = min(ans, dp[N][j]);
   return ans;
}

int main(){
   while(cin >> N >> M){
      if(N==0 && M==0)break;

      rep(i,M)scanf("%d",&c[i]);
      rep(i,N)scanf("%d",&x[i]);

      cout << solve() << endl;
   }
   return 0;
}