[Beijing wc2012]最多的方案

Description
第二关和很出名的斐波那契数列有关,地球上的OIer都知道:F1=1, F2=2, Fi = Fi-1 + Fi-2,每一项都可以称为斐波那契数。现在给一个正整数N,它可以写成一些斐波那契数的和的形式。如果我们要求不同的方案中不能有相同的斐波那契数,那么对一个N最多可以写出多少种方案呢?

Input
只有一个整数N。
Output
一个方案数
Sample Input
16

Sample Output
4
HINT

Hint:16=3+13=3+5+8=1+2+13=1+2+5+8

对于30%的数据,n<=256

对于100%的数据,n<=10^18


明显的记忆化搜索。

但是这道题有一个很重要的剪枝,因为斐波那契数列有注明前缀和公式 f(1)+f(2)+…+f(x)=f(x+2)-1。

当首项为 1 1时,这道题首项为1 2,也是类似的可以容错剪枝。


AC代码:

 #pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,f[110],cnt=2;	map<int,int> mp[110];
int solve(int x,int s){
	if(s>=f[x+2]&&f[x+2])	return 0;
	if(!s)	return 1;	
	if(!x)	return (s==0);
	if(mp[x][s])	return mp[x][s];
	int res=0;
	if(f[x]<=s)	res+=solve(x-1,s-f[x]);
	res+=solve(x-1,s);
	return mp[x][s]=res;
}
signed main(){
	cin>>n;
	f[1]=1,f[2]=2;
	while(1){
		f[++cnt]=f[cnt-1]+f[cnt-2];
		if(f[cnt]>n||f[cnt]<0)	break;
	}
	cnt--;
	cout<<solve(cnt,n);
	return 0;
}
[Beijing wc2012]最多的方案[Beijing wc2012]最多的方案 青烟绕指柔! 发布了484 篇原创文章 · 获赞 241 · 访问量 3万+ 私信 关注
上一篇:蓝桥杯 字符串对比 模拟


下一篇:基础练习 字符串对比