题解 P3539 【[POI2012]ROZ-Fibonacci Representation】

Nemlit

2018-07-26 17:02:17

Solution

# ~~论map(记忆化搜索)的强大~~ ![luogu](https://cdn.luogu.com.cn/upload/pic/25311.png) 70分(没开long long) 0分(注释忘记删掉了) 90分(被卡了16ms) 90分(拼命卡小常数比如 /2 -> >>1, scanf -> qread(), min(a+c,b+c ) -> min(a,b)+c ………………) 结果一共卡了8ms 正当我准备放弃此题时,我突然想到了什么, 有十组数据,每一组之间都有大量重复计算,难道不可以用记忆化搜索吗? 于是我看了下数据范围:K<1e17 (⊙o⊙)… 于是我就开始用了map来进行记忆化搜索。 虽然多了一个log的常数 于是瞬间由 1052ms ->0ms 此题的关键在于贪心策略:ans=min(cc[x-fab[t]],cc[fab[t+1]-x])+1 “+1”是因为选了一个数,于是答案就要加一 “t”的意思是斐波那契数列的第t项是比n小的最大fab 所以“t+1”的意思就是fab比n大的最小整数 我们不难发现找到了离n最近的两个数后,只要重新递归x-fab[t]和fab[t+1]-x即可 这个贪心要怎么证明呢? 因为斐波那契数列第n项是等于n-1项和n-2项之和,所以选择离目标数最近的数肯定比选择其他数要好(额,好像是废话) 各位神老也可以用反证法来证明,即如果我们不选择离目标数最近的fab答案还会不会是最优解 贴上AC代码(由于我太弱了,不会用STL二分,于是我写了一个手写二分来找到离目标数最近的fab[t]): ```cpp #include<bits/stdc++.h> using namespace std; #define ll long long inline ll read(){ register ll c = getchar(), x = 0; while(!isdigit(c)) c = getchar(); while(isdigit(c)) x = (x<<3)+(x<<1)+(c^48), c = getchar(); return x; } ll n,fab[95]; map<ll,ll> cc; inline ll check(ll t) { int l=1,r=90; while(r-l>1) { int mid=(l+r)>>1; //cout<<mid<<' '<<l<<' '<<r<<endl;; if(fab[mid]<t) { l=mid; } else { r=mid; } } return l; }//二分查找离目标数最近的fab[t] inline int s(ll x) { if(cc[x]) { return cc[x]; } if(x<=0) { return 0; } if(x==1) { return 1; } ll t=check(x); //cout<<"x = "<<x<<" t = "<<t<<endl; cc[x-fab[t]]=s(x-fab[t]); cc[fab[t+1]-x]=s(fab[t+1]-x); return min(cc[x-fab[t]],cc[fab[t+1]-x])+1; }//递归函数找出答案 int main() { int T=read(); fab[1]=fab[2]=1; for(register int i=3;i<91;i++) { fab[i]=fab[i-1]+fab[i-2]; //cout<<fab[i]<<' '; }//O(n)预处理出fab //cout<<check(4); while(T--) { n=read(); ll t=check(n); //cout<<t<<endl; printf("%d\n",min(s(n-fab[t]),s(fab[t+1]-n))+1); } return 0; } ``` # 复杂度………………大概是O(T n log log n)吧