Codeforces 454D - Little Pony and Harmony Chest

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 ;

}