uvalive5810 uva12368 Candles

题意：每组数据给出n个数，每个数在1-100，问组成这些数的蜡烛的权值的最小值。权值=把选的蜡烛从大到小排列组成的数

组成方式：比如有1 3两个蜡烛可以组成13（1和3）或4（1+3）只有一个加号可以用

解：位运算记录状态，can[i][j]表示在i的二进制所记录的状态下能不能组成j

can直接预处理出来，分类讨论用一个数表示还是用两个数表示 check的时候都在100以内直接枚举

 #include<cstdio>

 #include<cmath>

 #include<algorithm>

 #include<cstring>

 using namespace std;

 int n;

 bool can[][];

 int a[];

 int cas=;

 bool check1(int x,int y,int z){

     int cnt[];

     memset(cnt,,sizeof(cnt));

     int tmp=y;

     while (tmp!=){

             int now=tmp%;

             tmp=tmp/;

             if (((x&(<<now))==)||(cnt[now]>)) return false;

             cnt[now]++;

     }

     tmp=z;

     while (tmp!=){

             int now=tmp%;

             tmp=tmp/;

             if (((x&(<<now))==)||(cnt[now]>)) return false;

             cnt[now]++;

     }

     return true;

 }

 bool check(int x,int y){

     if ((y<)&&(x&(<<y))) return true;

     for (int i=;i<=y/;i++){

             if (i!=(y-i)){

                     if (check1(x,i,y-i)) return true;

             }

     }

     if (y==) return false;

     int tmpy1=y/;

     int tmpy2=y%;

     if (tmpy1==tmpy2) return false;

     if ((x&(<<tmpy1))==) return false;

     if ((x&(<<tmpy2))==) return false;

     return true;

 }

 int main(){

     memset(can,,sizeof(can));

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

             for (int j=;j<=;j++) can[i][j]=check(i,j);

     }

     while (){

             scanf("%d",&n);

             if (n==) return ;

             cas++;

             bool flag;

             int ans=;

             for (int i=;i<=n;i++) scanf("%d",&a[i]);

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

                     flag=true;

                     for (int j=;j<=n;j++) if (!can[i][a[j]]) flag=false;

                     if (flag){

                             int tmp=;

                             for (int j=;j>=;j--) if (i&(<<j)) tmp=tmp*+j;

                             if ((ans==)||(ans>tmp)) ans=tmp;

                     }

             }

             printf("Case %d: %d\n",cas,ans);

     }

     return ;

 }

 /*

 2 10 11

 1 30

 0

 */

巴特西

uvalive5810 uva12368 Candles

最新文章

热门文章