新手天翼
1083 围墙重建
题目描述 Description
为了给同学们营造一个良好的学习环境和方便学校的管理，市政府准备对小W就读的学校进行重新规划,占地面积将再次扩大。学校通过领导会议决定，重建学校的围墙。由于学校太大，重建围墙也不是一件小项目，学校决定请专门的建筑公司来建筑。 许多建筑公司从网上得知这个消息后，纷纷来到学校，找到学校领导，对自己公司进行介绍，并希望能接下这个项目。学校领导对很多家公司印象都还不错，难以取舍，为了公平，学校决定通过竞标决定把这个项目交给哪家公司负责。这次竞标是由学校自主决定的，不但要注重建筑实力，而且还要看建筑公司是否有足够的智慧。 学校通过两轮选拔。第一轮，选出建筑实力较强的公司。进入第二轮后，由学校专门负责这个项目的领导进行智力考核。 领导说：为了美观，我们准备建设一面2米高的围墙，围墙建好后，墙外要贴上有图画的瓷砖,当然这就需要瓷砖越大越美观了。目前市面用的最大瓷砖是多大？ 公司：宽1米，长2米的 领导：哦，我们就用这种吧，我们学校需建筑N米长的围墙，如果用这种瓷砖来贴，总共有多少种贴法呢？ 公司：…………….（正在计算中……………）
输入描述 Input Description
输入文件为一个数N（1<N<10000），表示围墙的长度。
对于20%的数据，2<N<90；
对于60%的数据，2<N ≤1200；
对于100%的数据，2< N<10000。
输出描述 Output Description
输出一个数，表示如果用宽1米、长2米，贴在高2米，长N米的围墙上，最多有多少种贴法？（输出数据后需换行）
样例输入 Sample Input
【样例输入1】
4
【样例输入2】
6
样例输出 Sample Output
【样例输出1】
5
【样例输出2】
13
数据来源 Source
合肥市26届信息学竞赛第二题
新手天翼
＠所有人，help me!!
资深天翼
不会，但要用递推！
资深光能
这道题挺硬核的，我做了半天，结果……放弃了。
反正要用高精度，我的游戏秘籍下一次更新正好讲高精，所以你等等吧！
初级光能
这题要用递推，其实这题难点是高精度！
输入n;
s1="1";
s2="2";
for(int i=2;i<n;i++) {
清空a,b;(memset)
用a[0]和b[0]分别存储s1.size(）和s2.size();
for j=1~a[0]
a[j]=s1[a[0]-j]-'0';
for j=1~b[0]
b[j]=s2[b[0]-j]-'0';
c[0]=max(a[0],b[0]);
for j=1~j<=c[0];j++) {
c[j]等于a[j]加b[j]加jw;
jw等于（c[j]除以10）;
c[j]模10;
}
如果jw比零大：{
c[0]++;
c[c[0]]=jw;
}
s1=s2;
s2="";
for(int j=1;j<=c[0];j++)
s2=char(c[j]+'0')+s2;
}
输出s2;（祝贺您会Accepted！！）
望采纳！！！
高级天翼
这是历代boss
