poj 2506 Tiling <dp+大数加法>

发布时间：2020-12-14 02:23:29 所属栏目：大数据来源：网络整理

导读：Tiling Time Limit: 1000MS ? Memory Limit: 65536K Total Submissions: 8305 ? Accepted: 4004 Description In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles? Here is a sample tiling of a 2x17 rectangle. Input Input is a sequence

Tiling

Time Limit: 1000MS	?	Memory Limit: 65536K
Total Submissions: 8305	?	Accepted: 4004

Description

In how many ways can you tile a 2xn rectangle by 2x1 or 2x2 tiles?
Here is a sample tiling of a 2x17 rectangle.

Input

Input is a sequence of lines,each line containing an integer number 0 <= n <= 250.

Output

For each line of input,output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

Sample Input

Sample Output

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

Source

The UofA Local 2000.10.14

思路：

????????? 这道题用到了动态规划的思想来进行递推操作的，动态规划有两个性质：1.最优子结构的性质；2.子问题重叠的性质！（这个性质比较明显！）

??????????首先这道题我们采用自顶向下的思路来进行思考，就是1.假设已经排好了n-1个矩形，就剩下一个矩形了，这时我们就只有一种方法；2.假设我们排好n-2个矩形了，就剩下两个矩形的位置了，这时候有3种排法，但是遇到了一个问题，在这3种方法中有一种方法会与1的有重叠，这时我们要将这种方法舍弃掉所以就只剩下2种方法了，通过这样的分析，我们得到一个公式：

?????????????????????????????????????????????????????? f(n)=f(n-1)+2*f(n-2);

这里面矩形的种类比价多，所以要用大数加法！

注意：这道题有一个坑：在n等于0的时候，需要输出1，不知道什么情况，记住就行了！

代码：

#include <stdio.h>
#include <string.h>
char a[300][5000];
int b[5000],c[5000];
int n;
int len1,len2;
int i,j,k;
void f()
{
	memset(b,sizeof(b));
	memset(c,sizeof(c));
	int t;
	for(j=len1-1,t=0;j>=0;j--)//反向赋值，将低位赋值给数组下标为0的元素，先加低位，再加高位 
	{
		b[t++]=2*(a[i-2][j]-'0');
	}
	for(j=len2-1,t=0;j>=0;j--)
	{
		c[t++]=a[i-1][j]-'0';
	}
	for(j=0;j<1000;j++)//从低位向高位加 
	{
		b[j]+=c[j];
		if(b[j]>=10)//进位 
		{
		    b[j+1]+=b[j]/10;//要注意这一点不要将这个语句与下面的语句写反了，否则会出错！ 
			b[j]=b[j]%10;
			
		}	
	}
	t=0;
	for(j=999;j>=0&&b[j]==0;j--);//将得到的结果重新赋值给下一个数组a,然后重新计算后面的值！ 
	if(b[j]!=0)
	{
		for(;j>=0;j--)
		{
			a[i][t++]=b[j]+'0';
		}
	}
}
int main()
{
	
	while(scanf("%d",&n)!=EOF)
	{
		memset(a,sizeof(a));
		a[0][0]='1';
		a[1][0]='1';a[2][0]='3';
		for(i=3;i<=n;i++)
		{
			len1=strlen(a[i-2]);
			len2=strlen(a[i-1]);
			f();
		}
		printf("%sn",a[n]);//输出！ 
	}
	return 0;
}

搜索

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

poj 2506 Tiling &lt;dp+大数加法&gt;

poj 2506 Tiling <dp+大数加法>