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;
}