首页 > 代码库 > 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] 递推 高精度
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。