做两个网站 之间超链接,蝉知和wordpress,网页编辑面试知识,济南建网站http://www.lydsy.com/JudgeOnline/problem.php?id2660 很容易想到是先把n表示成最大的两个斐波那契数相加#xff0c;然后再拆分这两个斐波那契数 把数表示成斐波那契进制的形式#xff0c;第i位表示有没有第i个斐波那契数 比如16133 001001 那么拆分一个数就是把一个1…http://www.lydsy.com/JudgeOnline/problem.php?id2660 很容易想到是先把n表示成最大的两个斐波那契数相加然后再拆分这两个斐波那契数 把数表示成斐波那契进制的形式第i位表示有没有第i个斐波那契数 比如16133 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的方案数 如果这个位是1dp[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)/2dp[i-1][0]*(b[i]-b[i-1])/2 #includecstdio
#includealgorithmtypedef 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(t3;f[t-1]f[t-2]n;t) f[t]f[t-1]f[t-2];int m0;for(int it-1;i;--i)if(nf[i]) b[m]i,n-f[i];reverse(b1,bm1);dp[1][1]1;dp[1][0]b[1]-11;for(int i2;im;i){dp[i][1]dp[i-1][0]dp[i-1][1];dp[i][0]dp[i-1][1]*(b[i]-b[i-1]-11)dp[i-1][0]*(b[i]-b[i-1]1);}printf(%lld,dp[m][0]dp[m][1]);
} 转载于:https://www.cnblogs.com/TheRoadToTheGold/p/8267443.html
