[CF453B]Little Pony and Harmony Chest

题目大意：

给你一个长度为\(n(n\le100)\)的正整数序列\(A(A_i\le30)\)，求一个正整数序列\(B\)，使得\(\sum_{i=1}^n |A_i-B_i|\)最小，且\(B\)中所有互质。

思路：

由于\(B_i\ge59\)时用\(1\)代替时不会更差，因此我们只需要考虑\(B_i\le58\)的情况。由于质因数只有\(16\)个，因此可以状压DP。另外记录转移即可。

源代码：

#include<cstdio>

#include<cctype>

#include<climits>

#include<algorithm>

inline int getint() {

	register char ch;

	while(!isdigit(ch=getchar()));

	register int x=ch^'0';

	while(isdigit(ch=getchar())) x=(((x<<2)+x)<<1)+(ch^'0');

	return x;

}

typedef long long int64;

const int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53};

const int N=101,P=16,B=59,S=1<<P;

int a[N],b[N],s[B],f[N][1<<P],g[N][1<<P];

inline void upd(int &a,const int &b) {

	a=std::min(a,b);

}

int main() {

	const int n=getint();

	for(register int i=2;i<B;i++) {

		for(register int j=0;j<P;j++) {

			if(i%p[j]==0) s[i]|=1<<j;

		}

	}

	for(register int i=1;i<=n;i++) {

		a[i]=getint();

	}

	for(register int i=1;i<=n;i++) {

		std::fill(&f[i][0],&f[i][S],INT_MAX);

		for(register int j=0;j<S;j++) {

			for(register int k=1;k<B;k++) {

				if(j&s[k]) continue;

				int &x=f[i][j|s[k]],y=f[i-1][j]+std::abs(a[i]-k);

				if(y<x) {

					x=y;

					g[i][j|s[k]]=k;

				}

			}

		}

	}

	int last=0;

	for(register int i=0;i<S;i++) {

		if(f[n][i]<f[n][last]) last=i;

	}

	for(register int i=n;i>=1;i--) {

		b[i]=g[i][last];

		last^=s[g[i][last]];

	}

	for(register int i=1;i<=n;i++) {

		printf("%d%c",b[i]," \n"[i==n]);

	}

	return 0;

}