首页 > 其他 > 详细

Codeforces 126D Fibonacci Sums 求n由任意的Sum(fib)的方法数 dp

时间:2014-06-25 08:44:31      阅读:348      评论:0      收藏:0      [点我收藏+]

题目链接:点击打开链接

题意:

给定一个数n

问把这个数拆成多个不相同的fibonacci数

有多少种拆法


#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
#include<math.h>
#include<set>
#include<queue>
#include<vector>
#include<map>
using namespace std;
#define ll __int64
#define N 90
ll n ,m;
ll f[N], dp[N][2]; //dp[i][0]表示不拆分下标为i的数 dp[i][1]表示拆分下标为i的数
vector<int>G;
int main(){  
	ll i, j, u, v, T; cin>>T;
	f[1] = 1; f[2] = 2;
	for(i=3;i<N;i++)f[i] = f[i-1] + f[i-2];
	while(T--) {
		G.clear();	cin>>n;
		for(i = N-1; i; i--) {
			if(f[i]<=n) {
				G.push_back(i);
				n -= f[i];
			}
		}
		reverse(G.begin(), G.end());
		dp[0][0] = 1;
		dp[0][1] = (G[0]-1)>>1;
		for(ll i = 1; i < G.size(); i++) {
			dp[i][0] = dp[i-1][0] + dp[i-1][1];
			dp[i][1] = dp[i-1][0] * ((G[i]-G[i-1]-1)/2) + dp[i-1][1] * ((G[i]-G[i-1])/2);
		}
		cout<<dp[G.size()-1][0]+dp[G.size()-1][1]<<endl;
	}
	return 0;
}


Codeforces 126D Fibonacci Sums 求n由任意的Sum(fib)的方法数 dp,布布扣,bubuko.com

Codeforces 126D Fibonacci Sums 求n由任意的Sum(fib)的方法数 dp

原文:http://blog.csdn.net/qq574857122/article/details/34120269

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!