题目链接

bzoj2660: [Beijing wc2012]最多的方案

题解

对于一个数的斐波那契数列分解，他的最少项分解是唯一的

我们在拆分成的相临两项之间分解后者，这样形成的方案是最优且不重的

我们可以把它的分解某一项拆分

设dp[i][1/0]表示对于最少拆分成的第i项斐波那切数拆不拆

在上一项j与这一项i的斐波那契数之间拆i项共有（i-j）/2种拆分方法，

转移方程就有了

代码

/*

对于一个数的斐波那契数列分解，他的最少项分解是唯一的

我们在拆分成的相临两项之间分解后者，这样形成的方案是最优且不重的

我们可以把它的分解某一项拆分

设dp[i][1/0]表示 对于最少拆分成的第i项斐波那切数拆不拆

在上一项j与这一项i的斐波那契数之间拆i项共有（i-j）/2种拆分方法，

转移方程就有了

*/

#include<vector>

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

inline int read() {

    int x = 0,f = 1;char c = getchar();

    while(c < '0'||c > '9')c = getchar();

    while(c <= '9' &&c >= '0')x = x * 10 + c - '0',c = getchar();

    return x * f;

}

LL f[107];

int a[107],tmp[107];

LL dp[107][2];

int main() {

	f[1] = 1;f[2] = 2;

	LL n;

	scanf("%lld",&n);

	int num = 3; for(num = 3;;++ num) {f[num] = f[num - 1] + f[num - 2]; if(f[num] > n) break;}

	int sum = 0;

	for(int i = num;i >= 1;-- i) if(n >= f[i]) n -= f[i],tmp[++ sum] = i;

	for(int cnt = 0,i = sum;i >= 1;-- i) a[++ cnt] = tmp[i];

	dp[1][1] = 1;

	dp[1][0] = a[1] - 1 >> 1;

	for(int i = 2;i <= sum;++ i) {

		dp[i][1] = dp[i - 1][1] + dp[i - 1][0];

		dp[i][0] = dp[i - 1][1] * (a[i] - a[i - 1] - 1 >> 1) + dp[i - 1][0] * (a[i] - a[i - 1] >> 1);

	}

	printf("%lld\n",dp[sum][1] + dp[sum][0]);

	return 0;

}

巴特西

bzoj2660: [Beijing wc2012]最多的方案

题目链接

题解

代码

最新文章

热门文章