P4133 [BJOI2012] 最多的方案

dzy15373891653 · 2025-07-19 20:16:52 · 个人记录

#include <iostream>
#include <map>
#define int long long//千万要记得开long long 

using namespace std;

const int N = 88;

int n,f[N + 5],s[N + 5];//注意数组加5，防止越界 
map<pair<int,int>,int> m;//map第一位存还剩多少可以选，二位表示选到第i位了 

int dfs (int x,int now) {//x表示还剩x的数值可以选，now表示当前是第now个斐波那契数 
//  cout << x << ' ';
    if (x < 0) return 0;//如果说还剩得数已经是负数了，代表永远也选不到了，直接返回0，代表方案数是0 
    if (m.count({x,now})) return m[{x,now}];//记忆化搜索，表示map数组里要是有这个数的方案总数的话，直接返回。 
    if (now == 0 && x == 0) return 1; //如果说还剩得数是零，且还能选的数是0，代表必须全部选完才能凑出来，代表方案数是1 
    if (s[now - 1] < x) return m[{x,now}] = dfs (x - f[now],now - 1);//如果说前now - 1个斐波那契数的和都小于要选的数的话，那第now个数必须得选，否则就凑不够x了，不用担心减完会是负数，因为有if语句帮忙兜底 
    if (f[now] > x) return m[{x,now}] = dfs (x,now - 1);//如果说当前的数大于x就不选，往前找，直到能选上为止 
    return m[{x,now}] = dfs (x - f[now],now - 1) + dfs (x,now - 1);//返回选或不选的方案总数之和 
}

signed main () {

    cin >> n;

    f[0] = f[1] = s[1] = 1;//斐波那契数第一和第二个设为1 

    for (int i = 2;i <= N;i ++) {
        f[i] = f[i - 1] + f[i - 2];//从二开始初始化斐波那契 
        s[i] = s[i - 1] + f[i];//s表示前i个斐波那契数的前缀和 
    }

//  for (int i = 1;i <= N;i ++) {
//      cout << s[i] << ' ';
//  }

    cout << dfs (n,88) << '\n';//dfs，n表示还剩n可以减，88表示当前的斐波那契数 
    return 0;
}