首页 > 代码库 > HDU 1041[Computer Transformation] 递推 高精度

HDU 1041[Computer Transformation] 递推 高精度

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1041

题目大意:初始数字1。规则1变成01,0变成10。问经过N次完整变换后,有多少连续零对。

关键思想:考虑零对的直接来源只有"10",而"10"的直接来源只有”1“或者”00“。于是可以得到以下几种递推式

1. dp[i]=pow(2,i-3)+dp[i-2];当前层多少1,下一层就多少10,下下层就多少00;当前层多少00,下一层就多少10,,下下层就多少00
2. dp[i]=dp[i-1]+2*dp[i-2];

通项公式为:((2^n+1)+(-1)^n)/3

代码如下:

#include <iostream>
#include <cmath>
using namespace std;
int dp[1010][1010];
//通项公式:div(add(Pow("2",n-1),"1"),3)
//1.dp[i]=pow(2,i-3)+dp[i-2];
//2.dp[i]=dp[i-1]+2*dp[i-2]
//代码中所用为递推式2 
void solve(){
	int c=0;
	for(int i=4;i<1002;i++){
		for(int j=1;j<1010;j++){
			dp[i][j]=2*dp[i-2][j]+dp[i-1][j]+c;
			c=dp[i][j]/10;
			dp[i][j]%=10;
			if(dp[i][j]==0&&c==0&&j>=dp[i-1][0]){
				dp[i][0]=j-1;
				break;
			}//保存大数长度 
		}
	}
	return;
}
void print(int n){
	for(int i=dp[n][0];i>=1;i--){
		printf("%d",dp[n][i]);
	}
	cout<<endl;
}

int main(){
	int n;
	dp[0][1]=0,dp[0][0]=1;
	dp[1][1]=0,dp[1][0]=1;
	dp[2][1]=1,dp[2][0]=1;
	dp[3][1]=1,dp[3][0]=1;
	solve();
	while(cin>>n){
		print(n);
	}
	return 0;
}

  

HDU 1041[Computer Transformation] 递推 高精度