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

我好蒻呀 · 2020-02-02 12:36:03 · 题解

给定正整数 k，求用斐波那契数的和或差表示 k 所需要的斐波那契数数量最小值。

k \leq 4\times 10^7

时空限制：\texttt{1s/125MB}

题解界面 LaTeX 渲染可能会有点问题，建议到博客中查看：题解 P3539 【[POI2012]ROZ-Fibonacci Representation】

这题的贪心做法是这样的：每次找到一个离 k 最近的斐波那契数 F_i，令 k\leftarrow|k-F_i|，重复若干次直到 k=0。（即每次令 k \leftarrow \min|k-F_i|）

但是我在网上一直找不到比较好的证明，非常自闭QAQ。

首先有几个性质：

• 存在最优方案，不会选择重复的一项。

  证明： 因为我们有 2F_i=F_{i+1}+F_{i-2}。

• 存在最优方案，不会选择相邻的两项。

  证明： 通过讨论可以知道

  +F_i+F_{i+1}=+F_{i+2} +F_i-F_{i+1}=-F_{i-1} -F_i+F_{i+1}=+F_{i-1} -F_i-F_{i+1}=-F_{i+2}

• 若当前 F_i \leq k \leq F_{i+1}，那么存在最优方案，一定包含了 F_i 或 F_{i+1}。

  证明： 反证法。假设不包含 F_i 和 F_{i+1}。那么根据不选相邻和重复的原则，我们可以证明其他部分的斐波那契数通过加减一定无法凑到 [F_i,F_{i+1}] 内的数。具体地，我们有 F_{i-1}+F_{i-3}+\cdots<F_i 成立，这是因为 F_1+F_3+\cdots +F_{2n-1}=F_{2n}-1 和 F_2+F_4+\cdots +F_{2n}=F_{2n+1}-1（为方便设 F_1=1,F_2=2）。

  这样一来，F_1\sim F_{i-1} 的数里选出来的和 S<F_i。同样我们如果用比 F_{i+1} 大的数拿去减，也会遇到这种的情况： F_{i+2}-S>F_{i+1} ，并且因为不能选相邻的，F_{i+4}-F_{i+2}>F_{i+3} 也是没用的。

  因此我们就证明了，存在最优方案，一定包含了 F_i 或 F_{i+1}。

那么接下来，我们就得到了，若当前 F_{i}\leq k \leq F_{i+1}，我们一定要从 F_i,F_{i+1} 中选一个。

接下来我们归纳证明，一定是选较近的那个斐波那契数：

• 显然对于满足 k < F_3 的 k，结论成立。
• 假设对于满足 k < F_i 的 k，结论是成立的，那么接下来考虑证明对于满足 F_i\leq k<F_{i+1} 的 k，有结论成立。不妨假设 k-F_i=a，F_{i+1}-k=b，不失一般性地，设 a<b，对于 a>b 同理。
• 接下来证明令 k\leftarrow a 的策略不比 k \leftarrow b 的策略劣。首先有 a+b=F_{i+1}-F_{i}=F_{i-1}。根据 a<b 我们有 b\in (\frac{F_{i-1}}2,F_{i-1}]，并且因为 F_{i-3}<\frac{F_{i-1}}{2}<F_{i-2}<F_{i-1}，而 \frac{F_{i-1}}2=\frac{F_{i-2}+F_{i-3}}2，因此离 b 最近的斐波那契数一定是 F_{i-2},F_{i-1} 之一。
• 因为 b \leq F_{i-1}<F_i 满足一定选离 b 较近的斐波那契数，因此我们有 b 的最优表示中一定有 F_{i-2},F_{i-1} 之一。那么 a=F_{i-1}-b，所以 a 可以由 b 的表达转化过来，并且 F_{i-1} 可以和 b 的表示中的 F_{i-2} 或是 F_{i-1} 合并/抵消，因此 a 均能得到一种不劣于 b 的表达方式。

至此我们证明了贪心策略的正确性。

显然，k 每次至少减少一半，所以答案是 \mathcal O(\log k) 级别的，这也是时间复杂度的级别。

#include <bits/stdc++.h>

typedef long long s64; 

const s64 lim = 4e17; 

int main()
{
    static s64 f[10001];

    int m = 2; 
    f[1] = 1, f[2] = 2; 
    while (f[m] <= lim)
    {
        ++m; 
        f[m] = f[m - 2] + f[m - 1]; 
    }

    int orzczk; 
    std::cin >> orzczk; 
    while (orzczk--)
    {
        s64 n; 
        int res = 0; 
        std::cin >> n; 
        while (n)
        {
            ++res; 
            int suf = std::upper_bound(f + 1, f + m + 1, n) - f; 
            n = std::min(f[suf] - n, n - f[suf - 1]); 
        }
        std::cout << res << '\n'; 
    }
    return 0; 
}