poj2506-Tiling(规律,大数)
发布时间:2020-12-14 02:23:37 所属栏目:大数据 来源:网络整理
导读:Tiling Time Limit: ?1000MS ? Memory Limit: ?65536K Total Submissions: ?8300 ? Accepted: ?4002 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 se
Tiling
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 2 8 12 100 200 Sample Output 3 171 2731 845100400152152934331135470251 1071292029505993517027974728227441735014801995855195223534251 这题主要是找寻规律,剩下的就是大数了! 我们假设要找2*n的种数: 2*(n-1)的已经拼好了,2*(n-2)也已经拼好了 我们可以知道,第n块只与n-1和n-1块有关系 第n-1块变成第n块只有一种方法 第n-2块变成第n块有三种方法,但是有一种和上边的那一种重复了 所以an=2*a(n-2)+a(n-1); 找出规律后代码也是可以优化的 未优化的 47ms: #include<cstdio> #include<cstring> using namespace std; struct node { int a[10000]; }s[300]; int main() { int c,n,i,j; s[0].a[0]=1; s[1].a[0]=1; for(i=2;i<260;i++) { c=0; for(j=0;j<10000;j++) { s[i].a[j]=s[i-1].a[j]+2*s[i-2].a[j]+c; c=s[i].a[j]/10; s[i].a[j]%=10; } } while(scanf("%d",&n)!=EOF) { for(i=10000-1;s[n].a[i]==0;i--); for(j=i;j>=0;j--) printf("%d",s[n].a[j]); printf("n"); } return 0; } 稍加优化 ?16ms: #include<cstdio> #include<cstring> using namespace std; struct node { int a[10000]; }s[300]; int main() { int c,j,cot=1; s[0].a[0]=1; s[1].a[0]=1; for(i=2;i<260;i++) { c=0; for(j=0;j<cot;j++) { s[i].a[j]=s[i-1].a[j]+2*s[i-2].a[j]+c; c=s[i].a[j]/10; s[i].a[j]%=10; } while(c) { s[i].a[cot++]=c%10; c/=10; } } while(scanf("%d",&n)!=EOF) { // for(i=10000-1;s[n].a[i]==0;i--); // for(j=i;j>=0;j--) // printf("%d",s[n].a[j]); // printf("n"); for(i=cot-1;s[n].a[i]==0;i--); for(;i>=0;i--) printf("%d",s[n].a[i]); printf("n"); } return 0; } 优化后 ? 0ms :
#include<cstdio> #include<cstring> using namespace std; struct node { int a[10000]; }s[300]; int main() { int c,cot=1; long long temp; s[0].a[0]=1; s[1].a[0]=1; for(i=2;i<260;i++) { c=0; for(j=0;j<cot;j++) { temp=s[i-1].a[j]+2*s[i-2].a[j]+c; c=temp/100000; s[i].a[j]=temp%100000; } if(c>0) { s[i].a[cot++]=c; } } while(scanf("%d",s[n].a[j]); // printf("n"); for(i=cot-1;s[n].a[i]==0;i--); printf("%d",s[n].a[i]); for(i-=1;i>=0;i--) printf("%05d",s[n].a[i]); printf("n"); } return 0; } (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |