http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2749&lang=jp
sortしてbit dp。
int N, M; int dp[(1 << 16) + 10][110]; int O[20]; int A[110]; void solve() { while(true) { cin >> N >> M; if(N == 0) break; rep(i, 0, N) cin >> O[i]; rep(i, 1, M + 1) cin >> A[i]; N++; O[N - 1] = 0; sort(A + 1, A + M + 1); rep(i, 0, (1 << N)) rep(j, 0, M + 1) dp[i][j] = inf; dp[0][0] = 0; rep(i, 0, (1 << N)) { rep(j, 1, M + 1) { int sum = 0; rep(k, 0, N) if(i & (1 << k)) sum += O[k]; MIN(dp[i][j], dp[i][j - 1] + abs(sum - A[j])); rep(k, 0, N) { if(!(i & (1 << k))) { MIN(dp[i | (1 << k)][j - 1], dp[i][j - 1]); MIN(dp[i | (1 << k)][j], dp[i][j - 1] + abs(sum + O[k] - A[j])); } } } } int res = inf; rep(i, 0, (1 << N)) { MIN(res, dp[i][M]); //debug(i, dp[i][M]); } cout << res << "\n"; } }
名前のインパクトが強すぎる。