首页 > 代码库 > uva 10254

uva 10254

2024-07-31 20:01:22   218人阅读

 如果我们设f[i]为4个柱子时把i个东东从一个柱子移到另一个柱子所用的最少步骤，设g[i]为3个柱子时对应的值，我们可以得到f[n]=min{2*f[k]+g[n-k]}，其中g[i]是已知的为2^i-1。

    然后接着就搞不下去了，看了别人报告说要找规律。有了上面的式子之后，我们打印前60个解还是很好打印的，同时把f[i]-f[i-1]也打印出来，这时会发现f[i]-f[i-1]都是2的某次方，而且2的k次方一共连续出现了k+1次，于是我们就可以以这个特征为依据预处理出所有解了

#include <iostream>#include <cstdio>#include <string.h>#include <algorithm>using namespace std;typedef long long ll;const int mod=100000000;struct Bignumber{     int V[50];     int len;     void clear(){         memset(V,0,sizeof(V));         len=1;     }     Bignumber operator *( int od){         Bignumber ans;         ans.clear();         for(int i=0; i<len; ++i){             ans.V[i]+=V[i]*od;             ans.V[i+1]+=(ans.V[i])/mod;             ans.V[i]%=mod;         }         ans.len=len;         while(ans.V[ans.len]>0){            ans.V[ans.len+1]+=ans.V[ans.len]/mod;            ans.V[ans.len]%=mod;            ans.len++;         }         return ans;     }     Bignumber operator +( Bignumber od){          Bignumber ans;          ans.clear();          int L=max(len,od.len);          for(int i=0; i<L; ++i){             ans.V[i]+=V[i]+od.V[i];             ans.V[i+1]+=ans.V[i]/mod;             ans.V[i]%=mod;          }          ans.len=L;          while(ans.V[ans.len]>0){            ans.V[ans.len+1]+=ans.V[ans.len]/mod;            ans.V[ans.len]%=mod;            ans.len++;            }            return ans;     }     void print(){         printf("%d",V[len-1]);         for(int i=len-2; i>=0; --i){             printf("%08d",V[i]);         }        // printf("\n");     }}F[10002];ll dp[65];ll f[65];int main(){    Bignumber t;    t.V[0]=1;    t.len=1;    F[0].clear();    int num=1,loc=1;    while(loc<=10000){           for(int i=0; i<num&&loc<=10000; ++i){              F[loc]=F[loc-1]+t; loc++;           }           num++;           t=t*2;      //     t.print(); printf("\n");    }    int n;    while(scanf("%d",&n)==1){         F[n].print();         printf("\n");    }    return 0;}
View Code

 

uva 10254


联系
我们