codeforcesRound#259(div2)D解题报告

解法：

这里题目给了几个很显眼的条件，ai限制在了1~30之间，由于可以bi无限选1这个数，那么|ai-bi| 最大就是29了，意味着bi < 59的。

要求所有的bi互质，可以化为所有的bi分解出来的质因数均不相同，bi < 59，有16个质数。这里我们很容易联想到状态压缩DP了。

用s表示当前阶段用了哪些质因数的状态，例如 s = 3 = 11 代表目前状态下使用了第一个和第二个质因数。

很快我们就可以写出状态转移方程：

f[i][s] = min(f[i-1][s^c[k]] + abs(a[i] - k))。 其中c[k]表示数字k使用了哪些质因数。

代码：

#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();
}