题意：求一个b数组，b数组中的所有数互质，和a数组对应下标的数的差的绝对值最小。
考虑a数组中的所有数范围为[1,30]则，b数组取值只有可能为[1,59)，因为如果取到59及其以后，肯定可以取1，59-30=30-1；而且1可以取多次，1与任何数互质。
然后首先需要把[2,59)之间的素数取出来，总共16个。然后状压，1代表那一位的素数因子是否存在。
d[i][s][0]表示递推到第i个位置的时候，为s状态下，第i个位置放的数。
d[i][s][1]表示递推到第i个位置的时候，为s状态下，最小值。
d[i][s][2]表示递推到第i个位置的时候，为s状态下，之前的状态。
st[i]表示当值为i的时候，素数因子的状态，初始化的时候全部算出。
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define mem(name,value) memset(name,value,sizeof(name))
#define FOR(i,n) for(int i=1;i<=n;i++)
using namespace std;
const int maxn=100+5;
const int inf=0x3f3f3f3f;
const int prime[20]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};
const int maxp = 16;
int st[maxn],d[maxn][1<<maxp][3],a[maxn],n;
void init(){
mem(st,0); mem(d,inf); mem(d[0],0);
for(int i=1;i<=59;i++)
for(int j=0;j<maxp;j++){
if(prime[j]>i) break;
if(i%prime[j]==0) st[i] |= (1<<j); //如果j为i的因子，则该位取1
}
}
void print(int cur,int pos){
if(cur==0) return ;
print(cur-1,d[cur][pos][2]);
if(cur==n) printf("%d\n",d[cur][pos][0]);
else printf("%d ",d[cur][pos][0]);
}
int main(){
//freopen("in.txt","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
init();
for(int i=1;i<=n;i++){
for(int j=1;j<59;j++){
int tmp = st[j];
for(int k=0;k<(1<<16);k++){
if(!(tmp&k)){
if(d[i-1][k][1]+abs(a[i]-j)<d[i][tmp|k][1]){
d[i][tmp|k][1] = d[i-1][k][1] + abs(a[i]-j);
d[i][tmp|k][0] = j;
d[i][tmp|k][2] = k;
}
}
}
}
}
int ans=inf,pos=0;
for(int i=0;i<(1<<16);i++){
if(d[n][i][1]<ans){
ans = d[n][i][1];
pos = i;
}
}
print(n,pos);
}
codeforces 453 B Little Pony and Harmony Chest (状压dp),布布扣,bubuko.com
codeforces 453 B Little Pony and Harmony Chest (状压dp)
原文：http://blog.csdn.net/u013791747/article/details/38386807