zoj 2341 Quantization Problem

zoj 2341 Quantization Problem

#include <cstring>#include <cstdlib>#include <cstdio>#include <iostream>#include <vector>#include <string>#include <queue>#include <algorithm>#include <cmath>#define MXN 100010#define MXM 100100#define Inf 0x3fffffff#define M0(a) memset(a, 0, sizeof(a))using namespace std;int T, n, m, s;int M[130][130], a[1010];int f[1010][130];int g[1010][130];int ansp[1010];void init(){ M0(M); scanf("%d", &n); for (int i = 1; i <= n; ++i) scanf("%d", &a[i]); scanf("%d%d", &m, &s); for (int i = 0; i < m; ++i) for (int j = 0; j < s; ++j) scanf("%d", &M[i][j]);}void solve(){ M0(f); for (int i = 1; i <= n; ++i) for (int j = 0; j < s; ++j) if (i == 1) f[i][j] = abs(M[0][j] - a[1]); else f[i][j] = Inf; M0(g); int nl; int ans = Inf, ansi = 0; for (int i = 1; i < n; ++i) for (int j = 0; j < s; ++j) if (f[i][j] < Inf){ nl = j % m; for (int k = 0; k < s; ++k) if (f[i][j] + abs(M[nl][k] - a[i + 1]) < f[i + 1][k]){ f[i+1][k] = f[i][j] + abs(M[nl][k] - a[i + 1]);  g[i+1][k] = j;  } } for (int i = 0; i < s; ++i) if (f[n][i] < ans){ ans = f[n][i]; ansi = i; } printf("%dn", ans); int cnt = 0, j = ansi; for (int i = n - 1; i > 0; --i){ ansp[i] = g[i+1][j]; j = g[i+1][j]; } for (int i = 1; i < n; ++i) printf("%d ", ansp[i]); printf("%dn", ansi);}int main(){ scanf("%d", &T); while (T--){ init(); solve(); if (T) puts("");  }}