ICPC 模擬国内予選2010C 差分パルス符号変調 AOJ 2199

簡単なDP。5秒考えればわかる。

#include <bits/stdc++.h>
using namespace std;

#define INF 2000000000

int dp[20010][260];
int c[20],x[20010];

int main(){

    int n,m;

    while(true){
        cin >> n >> m;
        if(n + m == 0)break;
        for(int i = 0;i < m;i++)cin >> c[i];
        for(int i = 0;i < n;i++)cin >> x[i];
        for(int i = 0;i < n+1;i++){
            for(int j = 0;j < 257;j++){
                dp[i][j] = INF;
            }
        }       
        dp[0][128] = 0;

        for(int i = 0;i < n;i++){
            for(int j = 0;j <= 255;j++){
                for(int k = 0;k < m;k++){
                    int ne = j + c[k];
                    ne = max(ne,0);
                    ne = min(255,ne);
                    dp[i+1][ne] = min(dp[i+1][ne], dp[i][j] + (x[i]-ne)*(x[i]-ne) );
                //    if(dp[i+1][ne] != INF)printf("dp[%d][%d] = %d\n",i+1,ne,dp[i+1][ne]);
                }
            }
        }
        int ans = INF;
        for(int i = 0;i <= 255;i++) ans = min(ans,dp[n][i]);
        cout << ans << endl;
    }
    return 0;
}