454D - Little Pony and Harmony Chest
思路：
状压dp，由于1的时候肯定满足题意，而ai最大是30，所以只要大于等于59都可以用1替换，所以答案在1到59之间
然后筛出1到58之间的质数，只有16个，把1到58的数的状态由这16个质数表示，如果整除这个质数则二进制中这一位为1，否则则为0
状态：dp[i][j]表示到第i个数为止选取的数的状态为j的最小差和
初始状态：dp[0][0]=0
状态转移：
dp[i+1][j|sta[k]]=min(dp[i+1][j|sta[k]],dp[i][j]+abs(k-a[i+1]))(j&sta[k]==0，1<=k<=58)
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
#define mem(a,b) memset(a,b,sizeof(a)) const int INF=0x3f3f3f3f;
int sta[];
int a[];
int res[];
int dp[][(<<)+];
int ans[][(<<)+];
int prime[]={,,,,,,,,,,,,,,,};
int getsta(int x){
int ans=;
for(int i=;i<;i++){
if(x%prime[i]==)ans|=<<i;
}
return ans;
}
void dfs(int n,int s){
if(n==)return ;
res[n]=ans[n][s];
dfs(n-,s^sta[res[n]]);
}
int main(){
ios::sync_with_stdio(false);
cin.tie();
for(int i=;i<;i++){
sta[i]=getsta(i);
}
int n;
cin>>n;
for(int i=;i<=n;i++)cin>>a[i];
mem(dp,INF);
mem(ans,-);
dp[][]=ans[][]=;
for(int i=;i<n;i++){
for(int j=;j<(<<);j++){
if(ans[i][j]==-)continue;
for(int k=;k<;k++){
if(j&sta[k])continue;
int s=j|sta[k];
if(ans[i+][s]==-||dp[i][j]+abs(k-a[i+])<dp[i+][s]){
dp[i+][s]=dp[i][j]+abs(k-a[i+]);
ans[i+][s]=k;
}
}
}
}
int mn=INF,s=;
for(int i=;i<(<<);i++){
if(dp[n][i]<mn){
mn=dp[n][i];
s=i;
}
}
dfs(n,s);
for(int i=;i<=n;i++)cout<<res[i]<<" ";
cout<<endl;
return ;
}