bzoj千題計劃213：bzoj2660: [Beijing wc2012]最多的方案

http://www.lydsy.com/JudgeOnline/problem.php?id=2660

?

很容易想到是先把n表示成最大的兩個斐波那契數相加，然后再拆分這兩個斐波那契數

把數表示成斐波那契進制的形式，第i位表示有沒有第i個斐波那契數

比如16=13+3 ? ? 001001

那么拆分一個數就是把一個1變成0，左邊的兩個0變成1

前面的1不影響后面

后面1拆出的兩個1不能拆到前面1的前面

所以b[i] 表示n的第i個1是第幾項斐波那契數

所以dp[i][0/1] 表示b中的i所在位（n的第b[i]個1）是0/1的方案數

如果這個位是1，dp[i][0]=dp[i-1][0]+dp[i-1][1]

如果這個位是0，即這個1被拆了，他能拆的次數是 與前面的1之間的0的個數/2

所以若i-1是1，兩個1之間有 b[i]-b[i-1]-1個0

若i-1是0，兩個1之間有b[i]-b[i-1]個0

dp[i][1]=dp[i-1][1]*(b[i]-b[i-1]-1)/2+dp[i-1][0]*(b[i]-b[i-1])/2

?

#include<cstdio>
#include<algorithm>typedef long long LL;using namespace  std;LL f[101];int b[101];LL dp[101][2]; int main()
{LL n;scanf("%lld",&n);f[1]=1; f[2]=2;int t;for(t=3;f[t-1]+f[t-2]<=n;++t) f[t]=f[t-1]+f[t-2];int m=0;for(int i=t-1;i;--i)if(n>=f[i]) b[++m]=i,n-=f[i];reverse(b+1,b+m+1);dp[1][1]=1;dp[1][0]=b[1]-1>>1;for(int i=2;i<=m;++i){dp[i][1]=dp[i-1][0]+dp[i-1][1];dp[i][0]=dp[i-1][1]*(b[i]-b[i-1]-1>>1)+dp[i-1][0]*(b[i]-b[i-1]>>1);}printf("%lld",dp[m][0]+dp[m][1]);
}

?

?