AOJ 2199 Differential Pulse Code Modulation
一個前で何を選択したか覚えておけばいいのでDPでした。
DP[前に何を選択したか] = そこに至るまでの最小二乗和です。
#include <iostream> #include <cstdio> #include <iomanip> #include <vector> #include <map> #include <set> #include <queue> #include <bitset> #include <stack> #include <utility> #include <numeric> #include <algorithm> #include <functional> #include <cctype> #include <complex> #include <string> #include <sstream> using namespace std; #define all(c) c.begin(),c.end() #define rall(c) c.rbegin(),c.rend() #define mp(a,b) make_pair((a),(b)) #define eq == typedef long long ll; typedef complex<double> point; typedef pair<int,int> pii; // →↑←↓ const int dx[] = {1,0,-1,0}; const int dy[] = {0,-1,0,1}; const double EPS = 1e-9; const int INF = 1 << 29; int main(){ while(true){ int N,M; cin >> N >> M; if(N == 0 and M == 0) break; vector<int> C(M); for(int i=0;i<M;i++) cin >> C[i]; vector<int> DP(256,INF); DP[128] = 0; for(int ind_n=0;ind_n<N;ind_n++){ vector<int> NEX(256,INF); int x; cin >> x; for(int j=0;j<=255;j++){ for(int i=0;i<M;i++){ if(DP[j] != INF){ int now = j + C[i]; if(now < 0) now = 0; else if(now > 255) now = 255; NEX[now] = min(NEX[now],DP[j]+(now-x)*(now-x)); } } } DP = NEX; } int mix = INF; for(int i=0;i<=255;i++){ mix = min(DP[i],mix); } cout << mix << endl; } return 0; }