AOJ 2749: ぼくのかんがえたさいきょうのおふとん

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";
	}
}

名前のインパクトが強すぎる。