POJ 1953World Cup Noise

题意:给出一个数n,求n位二进制中有多少个数不包含相邻的1.

普通的统计每一个数的话最大要统计2^45次,吃不消.

可以用dp一位一位做.

dp[i][0]表示长度位i的二进制当前位为0能有多少个数.

dp[i][1]表示长度位i的二进制当前位为1能有多少个数.

很容易可以得到方程:dp[i][0] = dp[i - 1][0] + dp[i - 1][1], dp[i][1] = dp[i - 1][0]

答案自然就是dp[n][0] + dp[n][1]

#include 
  
   
using namespace std;
const int MAX = 45;
long long dp[MAX][2];

void init(){
	dp[1][0] = dp[1][1] = 1;
	for(int i = 2; i < MAX; ++i){
		dp[i][0] = dp[i - 1][0] + dp[i - 1][1];
		dp[i][1] = dp[i - 1][0];
	}
}

int main(int argc, char const *argv[]){
	init();
	int T, caseno = 1;
	scanf("%d", &T);
	while(T--){
		int n;
		scanf("%d", &n);
		
		printf("Scenario #%d:\n%lld\n\n", caseno++, dp[n][0] + dp[n][1]);
	}
	return 0;
}