如何用长尾词策略优化POJ 2506 Tiling的解题思路？
- 内容介绍
- 文章标签
- 相关推荐
本文共计602个文字，预计阅读时间需要3分钟。
题目：平铺时间限制：1000MS 内存限制：65536K 总提交：7679 接受：3734描述：你有多少种方式可以用2x1或2x2的瓷砖来平铺一个2xn的矩形？以下是一个2x17矩形的样本平铺。输入：输入是一系列行“
Tiling
Time Limit:1000MS
Memory Limit:65536K
Total Submissions:7679
Accepted:3734
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
28 12 100 200
Sample Output
3171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
Source
The UofA Local 2000.10.14
规律很好找。q[i] = q[i-1] + q[i-2] * 2;
找到规律之后大数相加就可以了。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
int len;
int a[1000];
}q[1000];
int n;
int maxx(int aa,int bb)
{
if(aa>bb)
{
return aa;
}
else
{
return bb;
}
}
void ji(node &p)
{
for(int i=0;i<p.len;i++)
{
p.a[i] = p.a[i] * 2;
}
for(int i=0;i<p.len;i++)
{
if(p.a[i]>9)
{
p.a[i] = p.a[i] - 10;
p.a[i+1]++;
}
}
if(p.a[p.len]!=0)
{
p.len++;
}
}
void he(node x,node y,node &z)
{
int m = maxx(x.len,y.len);
for(int i=0;i<m;i++)
{
z.a[i] = x.a[i] + y.a[i];
}
for(int i=0;i<m;i++)
{
if(z.a[i]>9)
{
z.a[i] = z.a[i] - 10;
z.a[i+1]++;
}
}
if(z.a[m]!=0)
{
z.len = m + 1;
}
else
{
z.len = m;
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(q,0,sizeof(q));
q[0].len = 1;
q[0].a[0] = 1;
q[1].len = 1;
q[1].a[0] = 1;
for(int i=2;i<=n;i++)
{
ji(q[i-2]);
he(q[i-2],q[i-1],q[i]);
}
for(int i=q[n].len-1;i>=0;i--)
{
printf("%d",q[n].a[i]);
}
printf("\n");
}
return 0;
}
本文共计602个文字，预计阅读时间需要3分钟。
题目：平铺时间限制：1000MS 内存限制：65536K 总提交：7679 接受：3734描述：你有多少种方式可以用2x1或2x2的瓷砖来平铺一个2xn的矩形？以下是一个2x17矩形的样本平铺。输入：输入是一系列行“
Tiling
Time Limit:1000MS
Memory Limit:65536K
Total Submissions:7679
Accepted:3734
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
28 12 100 200
Sample Output
3171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251
Source
The UofA Local 2000.10.14
规律很好找。q[i] = q[i-1] + q[i-2] * 2;
找到规律之后大数相加就可以了。
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
struct node
{
int len;
int a[1000];
}q[1000];
int n;
int maxx(int aa,int bb)
{
if(aa>bb)
{
return aa;
}
else
{
return bb;
}
}
void ji(node &p)
{
for(int i=0;i<p.len;i++)
{
p.a[i] = p.a[i] * 2;
}
for(int i=0;i<p.len;i++)
{
if(p.a[i]>9)
{
p.a[i] = p.a[i] - 10;
p.a[i+1]++;
}
}
if(p.a[p.len]!=0)
{
p.len++;
}
}
void he(node x,node y,node &z)
{
int m = maxx(x.len,y.len);
for(int i=0;i<m;i++)
{
z.a[i] = x.a[i] + y.a[i];
}
for(int i=0;i<m;i++)
{
if(z.a[i]>9)
{
z.a[i] = z.a[i] - 10;
z.a[i+1]++;
}
}
if(z.a[m]!=0)
{
z.len = m + 1;
}
else
{
z.len = m;
}
}
int main()
{
while(scanf("%d",&n)!=EOF)
{
memset(q,0,sizeof(q));
q[0].len = 1;
q[0].a[0] = 1;
q[1].len = 1;
q[1].a[0] = 1;
for(int i=2;i<=n;i++)
{
ji(q[i-2]);
he(q[i-2],q[i-1],q[i]);
}
for(int i=q[n].len-1;i>=0;i--)
{
printf("%d",q[n].a[i]);
}
printf("\n");
}
return 0;
}