bzoj 2660: [Beijing wc2012]最多的方案【dp】

有点神奇的dp

首先注意到任意一个数都能被表示成若干个斐波那契数的和的形式

先求出n可以字典序最大的表示

设f[i][0/1]表示第i个斐波那契数选或者不选

如果当前数不选，那就选比他小的两个数，否则，需要不选比他小的两个数（连续的影响）

#include<iostream>

#include<cstdio>

using namespace std;

const int N=105;

long long n,a[N],s[N],top,f[N][2];

int main()

{

	scanf("%lld",&n);

	a[0]=1,a[1]=1;

	for(int i=2;i<=90;i++)

		a[i]=a[i-2]+a[i-1];

	for(int i=90;i>=1;i--)

		if(n>=a[i])

			n-=a[i],s[++top]=i;

	f[top][0]=(s[top]-1)/2,f[top][1]=1;

	for(int i=top-1;i>=1;i--)

	{

		f[i][1]=f[i+1][0]+f[i+1][1];

		f[i][0]=((s[i]-s[i+1]-1)/2)*f[i+1][1]+((s[i]-s[i+1])/2)*f[i+1][0];

	}

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

	return 0;

}

巴特西

bzoj 2660: [Beijing wc2012]最多的方案【dp】

最新文章

热门文章