UVA 4855 Hyper Box 斐波那契-白红宇

UVA 4855 Hyper Box 斐波那契

阅读量：4073 次

发布时间：2019-05-25

本文共 1085 字，大约阅读时间需要 3 分钟。

题目链接：https://icpcarchive.ecs.baylor.edu/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2856

比赛的时候和陈看了好长时间才看明白题意，和吴讨论做了出来，其实吴确实聪明，脑袋瓜子比较灵活

题意：有一个N维的空间，给你各维的长度，有一些n维的砖块，把空间填满，砖块不能交叉，空间不能一部分为空；求最少用的砖块

砖块各维都必须为斐波那契长度

思路：

空间各维分解，若是斐波那契数，不处理，若不是，求出最少用几个斐波那契数组成，最后相乘就是结果

难点在一个数最少由几个斐波那契数组成；

求出2.1亿内的所有斐波那契数，map映射为1，数组最少46；

初始为x,其实每次取不大于它的斐波那契数，并减去，更新x,重复上述；

代码：

#include
   
    #include
    #include
     
      #include
      
       using namespace std;long long a[20];long long b[49];int find(long long x){    bool str=true;    int num=0;    while(str)    {        int i=45;        while(i!=-1)        {            i--;            if(b[i]<=x)            {                x-=b[i];                num++;                break;            }        }        if(x==0)            break;    }    //cout<<"num== "<
       
        <
        
          s; s[1]++; s[2]++; for(i=2;i<47;i++) { b[i]=b[i-1]+b[i-2]; s[b[i]]++; } //cout<<"b[45]== "<
         
          <
          
           >t) { int p=1; while(t--) { int n; cin>>n; int i,j; long long k=1; for(i=0;i
           
            >a[i]; if(s[a[i]]==0) { k*=find(a[i]); } } cout<<"Case "<
            
             <<": "<
             
              <