codeforcesRound#259(div2)D解題報告

#include 
#include 
#include 
#define M_max 60
#define N_max 123
#define inf 0x3f3f3f3f

using namespace std;

int p[N_max], c[M_max], a[N_max];
int f[N_max][1<<16], pre[N_max][1<<16][2];
int n, cnt, minnum, minpos;


void prime() {
	for (int i = 2; i <= M_max; i++) {
	bool flag = false;

	for (int j = 2; j <= sqrt(i); j++)
	if (i%j == 0) {
	flag = true;
	break;
	}

	if (!flag) p[++cnt] = i;
	}

	for (int i = 1; i <= M_max; i++)
	for (int j = 1; j <= cnt; j++)
	if (i%p[j] == 0)
	c[i] |= 1 << (j-1);
}

void init() {
	prime();
	scanf("%d", &n);
	for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
}

void print(int x, int pos) {
	if (x == 0) return;
	print(x-1, pre[x][pos][0]);
	printf("%d ", pre[x][pos][1]);
}

void solve() {
	memset(f, inf, sizeof(f));
	memset(f[0], 0, sizeof(f[0]));
	minnum = inf;

	for (int i = 1; i <= n; i++)
	for (int s = 0; s < (1<<16); s++)
	for (int k = 1; k <= M_max; k++)
	if ((s&c[k]) == c[k]) {
	int tmp = f[i-1][s^c[k]] + abs(a[i]-k);

	if (tmp < f[i][s]) {
	f[i][s] = tmp;
	pre[i][s][0] = s^c[k];
	pre[i][s][1] = k;
	}
	}
	for (int s = 0; s < (1<<16); s++)
	if (f[n][s] < minnum) {
	minnum = f[n][s];
	minpos = s;
	}

	print(n, minpos);
}

int main() {
	init();
	solve();
}