Vijos 1921 严厉的班长【状态压缩动态规划】

严厉的班长
描述

木姑娘在班级里面是班长。虽然是副班长，却有着比正班长更高的威信，并深受小朋友们的爱戴。

每天眼保健操时间，木姑娘都要监督所有小朋友认真做眼保健操。整个过程被描述为n个时间段，第i个时间段内对于揉捏穴位的速度被要求为a[i]。

如果某一位小朋友在n个时间段内，速度分别为b[1],b[2],...,b[n]，则他的最终得分为 score = |a[1]-b[1]| + |a[2]-b[2]| + ... + |a[n]-b[n]|。

分数越大，则说明表现越差，如果b[1]到b[n]中，又满足任意两个数字均互素，则会受到木姑娘的严厉批评。

对于爱慕木姑娘的孩子来说，能和木姑娘有更多时间待在一起，才是最关键的。

格式

输入格式

第一行一个整数n，1<=n<=100。

第二行有n个整数，分别为a[1],a[2],...,a[n]且对于每一个a[i]满足1<=a[i]<=30。

输出格式

希望可以找出来一组b[1],...,b[n]满足score最小化，且b数组中的n个元素两两互素，并输出此刻的分数score。

样例1

样例输入1
5

1 1 1 1 1
Copy

样例输出1
0
Copy

样例2

样例输入2
5

1 6 4 2 8
Copy

样例输出2
3
Copy

限制

25%的数据，n<=10。
60％的数据，n<=30。
100％的数据，n<=100。

来源

感谢小岛

题目链接：

　　https://www.vijos.org/p/1921

题目大意：

　　题目给一个N个数的数列Ai，数大小不超过30，要求给出一组解Xi，使得解Xi Xj两两互质的情况下和原先数列的绝对值的差的和最小(min Σ|Ai-Xi|)，求这个和。

题目思路：

　　【状压DP】

　　首先考虑，因为要求两两互质，所以1肯定满足，那么取1<=Xi<2Ai-1(取2Ai-1和取1效果相同且更不易满足互质条件)

　　然后看2x30-1=59以内的质数，2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53 共16个。

　　也就是说当n>16时，多出来的必须用1，那么考虑数的大小可知尽量用1取对应小的数，于是排序的时候按从大到小排序，只做前16个，后面的全是1(当然前面也可以用1而不用质数)

　　所以问题转化为用16个质数的倍数去满足前16个数即可。将1~59质因数分解，记下每个数含有的质因数的二进制码，例如1为0，2为1，3为10，4为1，5为100，6为11 以此类推

　　DP的时候f[i][j]表示前i个数，质因数已经被选走的状态为j的最小和(j为16位二进制数)

　　考虑当前状态如果可行，就枚举当前的Xi，判断是否冲突，不冲突就更新新的f

 /****************************************************

     Author : Coolxxx

     Copyright 2017 by Coolxxx. All rights reserved.

     BLOG : http://blog.csdn.net/u010568270

 ****************************************************/

 #include<bits/stdc++.h>

 #pragma comment(linker,"/STACK:1024000000,1024000000")

 #define abs(a) ((a)>0?(a):(-(a)))

 #define lowbit(a) (a&(-a))

 #define sqr(a) ((a)*(a))

 #define mem(a,b) memset(a,b,sizeof(a))

 const double EPS=0.00001;

 const int J=;

 const int MOD=;

 const int MAX=0x7f7f7f7f;

 const double PI=3.14159265358979323;

 const int N=;

 const int M=;

 using namespace std;

 typedef long long LL;

 double anss;

 LL aans;

 int cas,cass;

 int n,m,lll,ans;

 int p[]={,,,,,,,,,,,,,,,};

 int a[N],fj[N];

 int f[N][M];

 void init()

 {

     int i,j,x;

     for(i=;i<;i++)

     {

         x=i;

         fj[i]=;

         for(j=;j<;j++)

         {

             while(x%p[j]==)

             {

                 x/=p[j];

                 fj[i]|=(<<j);

             }

             if(x==)break;

         }

     }

 }

 int main()

 {

     #ifndef ONLINE_JUDGE

 //    freopen("1.txt","r",stdin);

 //    freopen("2.txt","w",stdout);

     #endif

     int i,j,k;

     int x,y,z;

 //    for(scanf("%d",&cass);cass;cass--)

 //    for(scanf("%d",&cas),cass=1;cass<=cas;cass++)

     init();

     while(~scanf("%d",&n))

     {

         mem(f,0x7f);

         for(i=;i<=n;i++)

             scanf("%d",&a[i]);

         sort(a+,a++n,greater<int>());

         f[][]=;

         for(i=;i<=min(n,);i++)

         {

             for(j=;j<(<<);j++)

             {

                 if(f[i-][j]==MAX)continue;

                 for(k=;k<=a[i]+a[i]-;k++)

                 {

                     if(fj[k] & j)continue;

                     f[i][j|fj[k]]=min(f[i][j|fj[k]],f[i-][j]+abs(a[i]-k));

                 }

             }

         }

         ans=MAX;

         for(i=;i<(<<);i++)

             ans=min(ans,f[min(n,)][i]);

         if(n>)

         {

             for(i=;i<=n;i++)

                 ans+=a[i]-;

         }

         printf("%d\n",ans);

     }

     return ;

 }

 /*

 //

 //

 */

巴特西

Vijos 1921 严厉的班长【状态压缩动态规划】

严厉的班长

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

样例2

样例输入2

样例输出2

限制

来源

最新文章

热门文章

巴特西

Vijos 1921 严厉的班长 【状态压缩动态规划】

严厉的班长

描述

格式

输入格式

输出格式

样例1

样例输入1

样例输出1

样例2

样例输入2

样例输出2

限制

来源

最新文章

热门文章

Vijos 1921 严厉的班长【状态压缩动态规划】