题目链接：http://codeforces.com/contest/454/problem/D
题目大意：给出一个数组a，要求另一个数组b，满足数组b中的所有元素互质，且∑|ai-bi|(i：0~n)最小
思路：根据数据范围，（n<=100,a<=30）可以猜到状压 dp。对于一个数最差的情况就是取1了，那么对于30最远可以取到1或者59,所以b数组的范围为1-60.题目要求任意b中任意两个数互质，也即两个数不能有相同的素因子（同圣诞的晚宴）。
建立状态压缩模型：dp[i][j]表示前i个数在j状态下最少的代价，对于每个i，枚举前面（i-1）的所有状态，再枚举第i位要选的数，若没有冲突则dp转移
目标:min{dp[n][j]}
tick:同时用一个pre数组记录父状态，和mem数组记录每个选取状态的数，便于递归输出
代码：
#pragma warning(disable:4996)
#include<algorithm>
#include<cstdio>
#include<string>
#include<queue>
#include<stdlib.h>
#include<math.h>
#include<map>
#include<stdlib.h>
#include<stack>
#include<bitset>
#include<string.h>
#include<iostream>
#include<sstream>
#include<set>
using namespace std;typedef pair<int, int> pii;
typedef pair<double, int>pdi;
#define ll long long
#define CLR(a,b) memset(a,b,sizeof(a))
const int mod = 1e9 + 7;
const int maxn = 1e2 + 1;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;/*struct node {
ll x, y;
node() {}
node(ll _x, ll _y) :x(_x), y(_y) {}
};*/
//priority_queue<pdi, vector<pdi>, less<pdi> >q;int a[maxn];
int dp[maxn][1<<17];
int mem[maxn][1<<17];//记录当前一个状态取的数
int pre[maxn][1<<17];//前一个状态
int ans[maxn];
int prime[] = { 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59 };
int st[maxn];void init(void) {for (int i = 1; i < 59; i++) {for (int j = 0; j < 17; j++) {if (!(i%prime[j])) {st[i] |= (1 << j);}}}
}int main() {init();int n;scanf("%d", &n);CLR(dp, inf);CLR(dp[0], 0);int upp = (1 << 17);for (int i = 1; i <= n; i++)scanf("%d", &a[i]);for (int i = 1; i <= n; i++) {for (int j = 0; j<upp; j++) {for (int k = 0; k <= 60; k++) {if (!(st[k] & j)) {int tmp = dp[i - 1][j] + abs(a[i] - k);if (dp[i][j | st[k]] > tmp) {dp[i][j | st[k]] = tmp;mem[i][j | st[k]] = k;pre[i][j | st[k]] = j;}}}}}int minn = inf;int dex;for (int i = 0; i < upp; i++) {if (minn > dp[n][i]) {minn = dp[n][i];dex = i;}}for (int i = n; i>=1; i--) {int tt = mem[i][dex];ans[i] = tt;dex = pre[i][dex];}for (int i = 1; i <= n; i++) {if (i != 1)printf(" ");printf("%d", ans[i]);}
}