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