题目链接：HDU 1041
题目大意是，开始是1，以后1会变成01，0会变成10，问第n次转换共有多少对0（两个连续的0算一对）。
一个01会变为一个1001，一个1001会出现两个01；
打表推公式：
1 2 3 4 5 6
0 1 1 3 5 11
可以得到递推公式f(n)=f(n-1)+2*f(n-2)，注意先打表（我这地方错了，应该先打表，否则每个N都递推一遍很费时间），以后只需要查找即可，这个数会很大，需要采用大数处理（直接套加法模板，这地方数据小，用加法，不要用乘法，加法比乘法快很多）；
#include<iostream> #include<string> #include<algorithm> using namespace std; long long i,j,k,l,m,n,t,flag; string add(string s1,string s2) { int i,j,k,t; string sum; t=0; k=0; if(s2.size()>s1.size()) { s1.swap(s2); k=1; } for(i=0;i<s2.size();i++) { sum+=(s1[s1.size()-1-i]-'0'+s2[s2.size()-1-i]-'0'+t)+'0'; if((s1[s1.size()-1-i]-'0'+s2[s2.size()-1-i]-'0'+t)>=10)t=1; else t=0; } if(s1.size()==s2.size()&&t==1)sum+='1'; else { for(j=s1.size()-1-i;j>=0;j--) { sum+=(s1[j]-'0'+t)+'0'; if(s1[j]-'0'+t>=10)t=1; else t=0; } if(t==1)sum+='1'; } reverse(sum.begin(),sum.end()); return sum; } int main() { string s[1005],q; s[0]="0"; s[1]="0"; s[2]="1"; /*一开始的写法 while(cin>>n) { for(int i=3;i<=n;i++) { q=add(s[i-2],s[i-2]); s[i]=add(s[i-1],q); } cout<<s[n]<<endl; } 这样是过不去的，每输入一个n都会递推一次，很费时间，应该先打表； */ for(int i=3;i<=1000;i++) { q=add(s[i-2],s[i-2]); s[i]=add(s[i-1],q); } while(cin>>n) { cout<<s[n]<<endl; } }