luogu3539-POI

发表于 | 分类于

思路来源于黄学长.

由于f[i]*2=f[i]+f[i-1]+f[i-2]=f[i+1]+f[i-1]所以可得一定存在一组解使得每个斐波那契数最多只会出现一次。

我们按照这个思路来记忆化搜索。对于一个数可能由比它大的数转移而来也可能由比它小的数转移而来，且感性理解易证这个数一定是由大于它或小于它的第一个的斐波那契数转移而来。因此我们有转移方程f[x]=min(f[x-x1],f[x2-x])+1(其中x1为小于x的第一个斐波那契数，x2为大于x的第一个斐波那契数)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#include<iostream>
#include<cstring>
#include<cstdio>
#include<map>
#include<algorithm>
using namespace std;
long long f[100];
map<long long ,int> mp;
inline void tabl()
{
    f[0]=1;
    f[1]=1;
    for(int i=2;i<=90;i++)
        f[i]=f[i-1]+f[i-2];
}
int n;
long long x;
int dp(long long x)
{
    if(mp[x])return mp[x];
    int b=lower_bound(f,f+90,x)-f;
    if(f[b]==x)return 1;
    return mp[x]=min(dp(f[b]-x),dp(x-f[b-1]))+1;
}
int main()
{
    tabl();
    scanf("%d",&n);
    while(n--)
    {
        scanf("%lld",&x);
        printf("%d\n",dp(x));
    }
    return 0;
}