読者です 読者をやめる 読者になる 読者になる

AOJ 2199 Differential Pulse Code Modulation

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2199
 簡単な問題で詰まってしまい悔しいので反省文を残しておきます。
 y0 = 128 として
yi = yi-1 + (cに含まれる任意の数)
 で定められる数列ynをつくることを考えます。このとき、数列yと所与の数列xに対し、
sum = (y1 - x1) * (y1 - x1) + (y2 - x2) * (y2 - x2) + ... + (yn - xn) * (yn - xn)
が最小になるようにyを定め、その最小値を出力せよ、というのが問題。
 最初はこれは動的計画法だと無理っぽいなと思って考えこんでしまったのですが、動的計画法だと気づけば簡単です。
dp[i][j] = i番目までみて、yiの値がjのときの最小値
とします。そうしたら、すべてのdp[i][j]に対しどのc[k]を追加するか選ぶ、という操作を行えば問題が解けます。Nが大きいのと、dp[i + 1]はdp[i]にのみ依存することからメモリ節約型に書き換えます。
 問題は、どうしてdpで解く方法が思いつかないのか、ということ。この問題の場合、iまでの最小値を持っておいて貪欲に解を求めようとしても、二乗和はyiの値にも依存しますからうまくいきません。でも、可能なyiの値256通りでの最小値を持っておけば、そこから遷移する状態(M <= 16なのでかなり少ない)をすべてためすことで、可能なyi+1の値256通りに関する最小値が得られます。このように、一般の最小値をある特定の場合に関する最小値に限定して考えると単調な遷移になる、というのがうまく発想できていない気がします。反省ですね。

int square(int x){
    return x * x;
}
int compress(int x){
    if(x >= 256) return 255;
    if(x < 0) return 0;
    return x;
}
int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    while(cin >> N >> M && N){
        vector<int> c(M), x(N);
        rep(i, M) cin >> c[i];
        rep(i, N) cin >> x[i];
        vector<vector<int> > dp(2, vector<int>(256, INF));
        //dp[i][j] := i番目までみて、値がjのときの二乗和の最小値
        int crr = 0, nxt = 1;
        dp[crr][128] = 0;
        rep(k, N){
            rep(i, 256) dp[nxt][i] = INF;
            rep(i, 256) rep(j, M){
                int it = compress(i + c[j]);
                dp[nxt][it] = min(dp[nxt][it], dp[crr][i] + square(it - x[k]));
            }
            swap(crr, nxt);
        }
        int ans = INF;
        rep(i, 256) ans = min(ans, dp[crr][i]);
        cout << ans << endl;
    }
    return 0;
}