首页 > 代码库 > Codeforces Round #259 (Div. 2)-D. Little Pony and Harmony Chest

Codeforces Round #259 (Div. 2)-D. Little Pony and Harmony Chest

2024-07-15 11:48:40   214人阅读

题目范围给的很小，所以有状压的方向。

我们是构造出一个数列，且数列中每两个数的最大公约数为1;

给的A[I]<=30，这是一个突破点。

可以发现B[I]中的数不会很大，要不然就不满足，所以B[I]<=60左右。构造DP方程DP[I][J]=MIN(DP[I][J],DP[I][J^C[K]]+abs(a[i]-k));

K为我们假设把这个数填进数组中的数。同时开相同空间记录位置，方便输出结果。。

#include<iostream>#include<stdio.h>#include<string.h>#include<algorithm>#define inf 0x3f3f3f3fusing namespace std;int cnt=0;int c[123],a[123];int dp[101][(1<<16)+5];int pre[101][(1<<16)+5][2];int b[123]={0};int p[123];void prime()//帅选素数{   for (int i=2;i<60;i++)   if (!b[i])   {       p[++cnt]=i;       for (int j=i+i;j<60;j+=i)       b[j]=1;       }}int cal(int x)//对每个数分解素数{  int ans=0;  for (int i=1;i<=cnt;i++)  {      if (x%p[i]==0) ans|=(1<<(i-1));      while (x%p[i]==0) x/=p[i];  }  return ans;}void print(int x,int pos)//递归出数组{        if (x==0) return;        print(x-1,pre[x][pos][0]);        cout<<pre[x][pos][1]<<" ";}int main(){    int n;    prime();    cin>>n;    for (int i=1;i<=n;i++) cin>>a[i];    for (int i=1;i<60;i++)         c[i]=cal(i);    memset(dp,inf,sizeof(dp));    memset(dp[0],0,sizeof(dp[0]));//初始化        for (int i=1;i<=n;i++)      for (int j=0;j<(1<<16);j++)         for (int k=1;k<60;k++)          if ((j&c[k])==c[k]){//由前一个状态推后一个状态             int tmp=dp[i-1][j^c[k]]+abs(k-a[i]);               if (dp[i][j]>tmp)                {                 dp[i][j]=tmp;                 pre[i][j][0]=(j^c[k]);                 pre[i][j][1]=k;                }        }        int min=inf,pos;        for (int i=0;i<(1<<16);i++)        if (dp[n][i]<min)        {        min=dp[n][i];        pos=i;        }    print(n,pos);return 0;}
View Code

 


联系
我们