题解 P3539 【[POI2012]ROZ-Fibonacci Representation】
Nemlit
2018-07-26 17:02:17
# ~~论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)吧