題目描述

第二關(guān)和很出名的斐波那契數(shù)列有關(guān)，地球上的OIer都知道：F1=1, F2=2, Fi = Fi-1 + Fi-2，每一項都可以稱為斐波那契數(shù)。現(xiàn)在給一個正整數(shù)N，它可以寫成一些斐波那契數(shù)的和的形式。如果我們要求不同的方案中不能有相同的斐波那契數(shù)，那么對一個N最多可以寫出多少種方案呢？

輸入輸出格式

輸入格式：
只有一個整數(shù)N。

輸出格式：
一個方案數(shù)

輸入輸出樣例

輸入樣例#1： 復(fù)制
16
輸出樣例#1： 復(fù)制
4
說明
Hint：16=3+13=3+5+8=1+2+13=1+2+5+8

對于30%的數(shù)據(jù)，n<=256

對于100%的數(shù)據(jù)，n<=10^18

首先需要知道的是任何一個自然數(shù)可以像這樣被斐波那契數(shù)分解
我們又知道n>=3時斐波那契數(shù)可以被前兩個數(shù)的和替換
那么我們可以先貪心找到一種每個數(shù)最大的方案
然后嘗試將其中的數(shù)替換，使用dp計數(shù)
f[i][1/0] 表示最大分解中的第i個是否被替換（0表示被替換）
得到動規(guī)方程：

f[i][1]=f[i-1][1]+f[i-1][0]; f[i][0]=f[i-1][0]*(pos[i]-pos[i-1])/2 +f[i-1][1]*(pos[i]-pos[i-1]-1)/2;//ps:當(dāng)該數(shù)(pos[i])要分解時考慮pos[i-1]能否使用 //即若pos[i-1]被替換(f[i-1][0])則可使用，若沒替換則不行（-1即可）

code:

//By Menteur_Hxy #include <cstdio> #include <iostream> #include <algorithm> #include <cstring> #include <string> #include <map> #include <vector> #include <queue> #include <set> #include <ctime> #define M(a,b) memset(a,(b),sizeof(a)) #define F(i,a,b) for(register int i=(a);i<=(b);i++) #define LL long long using namespace std;inline LL rd() {LL x=0,fla=1; char c=' ';while(c>'9'|| c<'0') {if(c=='-') fla=-fla; c=getchar();}while(c<='9' && c>='0') x=x*10+c-'0',c=getchar();return x*fla; }inline void out(LL x){int a[25],wei=0;if(x<0) putchar('-'),x=-x;for(;x;x/=10) a[++wei]=x%10;if(wei==0){ puts("0"); return;}for(int j=wei;j>=1;--j) putchar('0'+a[j]);putchar('\n'); }const int MAX=1010; const int INF=0x3f3f3f3f; LL n,cnt,scnt; LL f[MAX][2],fib[MAX],pos[MAX];int main() {n=rd();fib[1]=1,fib[2]=2;for(cnt=3;fib[cnt-1]<=n;cnt++) fib[cnt]=fib[cnt-1]+fib[cnt-2];cnt--;for(int i=cnt;i>=1;i--) if(n>=fib[i]) {n-=fib[i]; pos[++scnt]=i;}sort(pos+1,pos+scnt+1);f[1][1]=1; f[1][0]=((pos[1]-1)>>1);F(i,2,scnt) {f[i][1]=f[i-1][0]+f[i-1][1];f[i][0]=f[i-1][0]*(pos[i]-pos[i-1]>>1) + f[i-1][1]*(pos[i]-pos[i-1]-1>>1);}out(f[scnt][0]+f[scnt][1]);return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/Menteur-Hxy/p/9139276.html

總結(jié)

以上是生活随笔為你收集整理的[luogu4133 BJOI2012] 最多的方案 (计数dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。