考试一看我就想到了状压dp。当时没有想到素数，以为每一位只有0~9这些数，就开始压了。后来发现是小于30，然后改到了15，发现数据一点不给面子，一个小点得数都没有，完美爆零。。
考虑到bi最多变成58，如果变成更大的数还不如变成1，而且58之内只有16个素数，所以就压这16个素数就行了。就是他们的素数因子。
f[i][j]表示到第i位质因数压进去状态为j时最短序列；
f[i][j|prime[k]]=min(f[i][j|prime[k]],f[i-1][j]+abs(a[i]-k));
注意排序一下这些数，找前16个就行，因为最多有16个素数，其他的就都是1了，不要忘了最后加上。
PS：我的代码打表打过去的。借用一下同学的。
#include
#include
#include
#include
#include
#include
using namespace std;
int n,ji=0,jishu,shu=0x7fffffff;
int a[150],b[150],prime[100],f[110][1<<16],zhi[70];
bool su[5050];
int pai(const int a,const int b)
{
return a>b;
}
int xiao(int x,int y)
{
if(x<=y) return x;
else return y;
}
int lowbit(int x)
{
return x&-x;
}
int zhao(int x)
{
int shu=0;
while(x>0)
{
if(x&1)
return shu;
x>>=1;
shu++;
}
return shu;
}
int count(int x)
{
int shu=0;
while(x>0)
{
if(x&1)
shu++;
x>>=1;
}
return shu;
}
int main()
{
//freopen("seq.in","r",stdin);
//freopen("seq.out","w",stdout);
memset(su,0,sizeof(su));
memset(f,0x3f,sizeof(f));
memset(prime,0,sizeof(prime));
memset(zhi,0,sizeof(zhi));
cin>>n;
for(int i=1;i<=n;++i)
cin>>a[i];
f[0][0]=0;
sort(a+1,a+n+1,pai);
su[1]=1;
for(int i=2;i<=10;++i)
for(int j=2;j<=50;++j)
su[i*j]=1;
for(int i=2;i<=58;++i)
if(su[i]==0)
prime[i]=++ji;
for(int i=2;i<=61;++i)
for(int j=2;j<=i;++j)
{
if(i%j==0&&prime[j]!=0)
zhi[i]|=(1<<(prime[j]-1));
}
for(int i=0;i
for(int j=0;j<(1<<16);++j)
for(int k=1;k<=60;++k)
{
if((j&zhi[k])==0)
f[i+1][j|zhi[k]]=xiao(f[i+1][j|zhi[k]],f[i][j]+abs(a[i+1]-k));
}
for(int i=0;i<(1<<16);++i)
if(f[xiao(n,16)][i]
shu=f[xiao(n,16)][i];
if(n<=16)
cout<<shu;
else
{
for(int i=17;i<=n;++i)
shu+=abs(a[i]-1);
cout<<shu;
}
//system("pause");
return 0;
}