题解 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】](https://www.luogu.com.cn/blog/samxiang/solution-p3539)
这题的贪心做法是这样的：**每次找到一个离 $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)$ 级别的，这也是时间复杂度的级别。
```cpp
#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;
}
```