AOJ 2199 - Differential Pulse Code Modulation

Differential Pulse Code Modulation | Aizu Online Judge

解説

dp[i][j] := i個目の信号まででyがjのときの最小値

コード

#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
#include <cmath>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <vector>
#include <stdlib.h>
#include <stdio.h>
#include <bitset>
#include <cstring>
using namespace std;
#define FOR(I,A,B) for(int I = (A); I < (B); ++I)
#define CLR(mat) memset(mat, 0, sizeof(mat))
typedef long long ll;
ll dp[20004][256]; 
int main()
{
  ios::sync_with_stdio(false);
  cin.tie(0);
  int N, M;
  while(cin>>N>>M,N||M) {
    int c[M]; FOR(i,0,M) cin >> c[i];
    int x[N]; FOR(i,0,N) cin >> x[i];
    FOR(i,0,N+1) FOR(j,0,256) dp[i][j] = 1e18;
    dp[0][128] = 0;
    FOR(i,0,N) {
      FOR(j,0,256) {
        if(dp[i][j] == 1e18) continue;
        FOR(k,0,M) {
          int y = max(0, min(255, j + c[k]));
          dp[i+1][y] = min(dp[i+1][y], dp[i][j] + (ll)(x[i]-y) * (ll)(x[i]-y));
        }
      }
    }
    ll ans = 1e18;
    FOR(i,0,256) ans = min(ans, dp[N][i]);
    cout << ans << endl;
  }
  return 0;
}