题解 P4133 【[BJOI2012]最多的方案】

我好蒻呀 · 2018-02-06 22:21:54 · 题解

分析

这题出得真是妙。
首先我们可以证明，任意自然数都能被不相同的斐波那契数之和表示：

具体的可以参考：Zeckendorf's theorem

简单证明：

可以考虑归纳，显然对于 n \leq 3 这个结论是成立的。

令 f_k 表示斐波那契数列的第 k 项，假设对于满足 n < f_{k} 的自然数都能被不相同的斐波那契数表示，那么对于 n=f_k 显然可以直接用 f_k 表示。

对于满足 f_k<n<f_{k+1} 的整数 n，因为 n<f_{k+1}\leq 2f_{k}，因此 n-f_k<f_k，所以 n-f_k 的斐波那契数表示中肯定不包含 f_k，我们可以考虑用 n-f_k 的斐波那契数表示加上 f_k，从而得到 n 的斐波那契数表示。

而斐波拉契数列的递推公式 f[i]=f[i-1]+f[i-2](i>2)告诉我们了一个性质：数列中的任何一项（非第一第二项）能且只能分解为前两项之和，也只有相邻两项能够合并成下一项。
于是我们先倒过来想，将方案中所有能合并的不断合并，得到一个没有相邻两项的方案，而这个方案显然可以通过贪心，不断从大往小取得到。
我们将这个贪心得到的数列中第 i 个数在斐波拉契数列中的编号记为 pos[i]，将这个方案所用元素个数记为 cnt。
则 n=\sum \limits_{i=1}^{cnt}f[pos[i]]。
根据前面的分解方式和得到的结论，我们能且只能找到一个这样不相邻的表示法（可以形象地理解，一种不相邻方案与另一种不相邻方案之间，其中一种的最大值比另一种的所有元素和还要来得大）。
接下来我们又反过来想，尝试在这个方案的基础上分解。
显然直接做是不可能的。
我们前面发现不相邻表示法是唯一的，这样我们可以考虑分阶段分解，想到DP。
令 g[i][0/1] 表示将 1...i 的元素进行变换后，恰好组成 \sum \limits_{j=1}^{i}f[pos[j]] 的方案数，第二维的 0/1 表示是/否分解第 i 个元素，且第 i 个阶段必须组成 f[pos[i]]，的方案数。
首先明确，若不分解第 i 个元素，则 (pos[i-1],pos[i]) 的元素都不用，下一阶段只能用 (pos[i],pos[i+1]]) 的元素分解。
否则若分解第 i 个元素，则用到 (pos[i-1],pos[i]) 或 [pos[i-1],pos[i]) 的元素（取决于 i-1 有没用上），下一阶段就能用 [pos[i],pos[i+1]]) 的元素分解。
而分解一个元素，需要它前两项的和，若这个和还能分解，则分解的必须是前一项。由此得到，分解一次需要两项是空出来的。
于是转移方程显然：

g[i][1]=g[i-1][1]+g[i-1][0]

g[i][0]=g[i-1][1]*((pos[i]-pos[i-1]-1)\ div\ 2)+g[i-1][0]*((pos[i]-pos[i-1])\ div\ 2)

初值也显然：g[1][1]=1,\ g[1][0]=(pos[1]-1)\ div\ 2

代码：

#include <cmath>
#include <cstdio>
#include <cctype>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>

typedef long long ll; 

const int MaxN = 110; 

ll n, f[MaxN]; 
int m, cnt, pos[MaxN]; 
int g[MaxN][2]; 

int main()
{
    std::cin >> n; 
    f[1] = 1, f[2] = 2; 
    for (m = 3; f[m - 1] <= n; ++m)
        f[m] = f[m - 1] + f[m - 2]; 
    --m; 
    for (int i = m; i >= 1; --i)
        if (n >= f[i])
        {
            n -= f[i]; 
            pos[++cnt] = i; 
        }
    std::sort(pos + 1, pos + cnt + 1); 
    g[1][1] = 1, g[1][0] = pos[1] - 1 >> 1; 
    for (int i = 2; i <= cnt; ++i)
    {
        g[i][1] = g[i - 1][0] + g[i - 1][1]; 
        g[i][0] = g[i - 1][1] * (pos[i] - pos[i - 1] - 1 >> 1) + g[i - 1][0] * (pos[i] - pos[i - 1] >> 1);  
    }

    printf("%d\n", g[cnt][0] + g[cnt][1]);  

    return 0; 
}