P4133 [BJOI2012] 最多的方案

#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;
}