2020 GDUT Rating Contest I (3.08) C. 積木

C. 積木

連結

題目描述

用積木塊來搭房子。

給出最長的積木塊的長度，該積木塊隻能當作地基。

如果目前搭建的房子的最頂端的積木塊的長度為k，可以選擇一個長度屬于[1,k/2]的積木放在房子的最頂端，或者選擇不再繼續放置積木。

求一共能搭建幾種房子。

題目分析

f(n)代表地基長度為n時的房子數量，先列舉前幾種情況看一看：

f(1)=1,f(2)=1+f(1)

f(3)=1+f(1),f(4)=1+f(2)+f(1)

f(5)=1+f(2)+f(1),f(6)=1+f(3)+f(2)+f(1)

… …

發現n為奇數時f(n)==f(n-1)，n為偶數時f(n)==f(n-1)+f(n/2)，經過思考發現十分合理。。。

代碼

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int mod=1e9+7;

int f[1000001]={0,1};

int main(){
	ll ans=1;
	int n;
	scanf("%d",&n);
	for(int i=2;i<=n;i++){
		if(i&1){
			f[i]=f[i-1];
		}
		else{
			f[i]=(f[i-1]+f[i/2])%mod;
		}
	}
	printf("%d\n",f[n]);
}