一些细节

Tanktt · 2020-10-27 19:53:08 · 个人记录

0x3f把每个字节都变成63-->10亿多

#include<bits/stdc++.h>
using namespace std;
int n,a[112],f[112][75536],num[1000],prime[112],sum,id[112][75536],pre[112][75536],b[112];
inline int calc(int x,int y)
{
    return (x-y)*(x-y);
}
int  main()
{
    freopen("sequence.in","r",stdin);
    freopen("sequence.out","w",stdout);
    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]);
    for (int i=2; i<=53; i++)
    {
        bool flag=0;
        for (int j=2; j<=i-1; j++)
        if (i%j==0) {flag=1; break;}
        if (!flag) prime[++sum]=i;
    }
    int pp=(1<<16)-1;
    for (int i=2; i<=60; i++)
    {
        for (int j=1; j<=sum; j++)
        if (i%prime[j]==0) num[i]|=(1<<j-1);
    }
    for (int i=0; i<=n+1; i++)
        for (int j=0; j<=pp; j++) f[i][j]=1000000012;
    f[0][0]=0;
    for (int i=1;i<=n; i++)
        for (int k=0; k<=pp; k++)
        {
            if (f[i-1][k]==1000000012) continue;
            if (f[i-1][k]+calc(1,a[i])<f[i][k])
            {
                f[i][k]=f[i-1][k]+calc(1,a[i]);
                id[i][k]=1;pre[i][k]=k;
            }
        for (int j=2; j<=60; j++)
            if (((num[j]&k)==0)&&
                f[i-1][k]+calc(j,a[i])<f[i][k|num[j]])
            {
                f[i][k|num[j]]=f[i-1][k]+calc(j,a[i]);
                //printf("%d %d %d\n",i,j,f[i][k|num[j]]);
                id[i][k|num[j]]=j;
                pre[i][k|num[j]]=k;
            }
        }
            int p=0,ans=1000000012;
    for (int i=0; i<=pp; i++)
    if (f[n][i]<ans)
    {
        ans=f[n][i];p=i;
    }
    for (int i=n; i>=1; i--)
    {
        b[i]=id[i][p];p=pre[i][p];
    }
    printf("%d\n",ans);
    for (int i=1; i<=n ;i++)
    {
        printf("%d%c",b[i],(i==n)?'\n':' ');
    }
    return 0;
}