UVA 11375 Mathes

发布时间:2016-12-6 20:15:00 编辑:www.fx114.net 分享查询网我要评论
本篇文章主要介绍了"UVA 11375 Mathes",主要涉及到UVA 11375 Mathes方面的内容,对于UVA 11375 Mathes感兴趣的同学可以参考一下。

题目来源:UVA - 11375 原题概述:问用n根火柴能摆出多少个非负整数? 不需用完全部火柴,不能有前导零(可以是整数0),如2根火柴只能摆出2. 分析:用d[i]表示状态:用i根火柴能构成的整数的个数。依此往后面添加数字x,就从状态i转移到状态i+c[x],c[x]代表数字x需要的火柴数。因此可以递推得出答案。 但是还存在两个问题:前导0的处理  和  大数运算。 1.   前导0 的处理 规定第一个数不允许添加0,即i==0 && j==0 时continue,从第二个数开始可以添加任何数,最后如果n>=6就+1. 2.   高精度运算 用数组存储数据,模拟手算过程。 个人体会: 需要注意细节,开始时犯过一个错误,每8位存在一个int型数中,忘了有前导0的情况,输出应该是%08d(除最高位)。 代码: #include<iostream> #include<cstdio> #include<cstring> #include<queue> #include<stack> #include<cmath> #include<algorithm> #include<cstdlib> #include<stack> #include<map> #include<vector> typedef long long LL; using namespace std; const int INF=0x3f3f3f3f; const int maxn=2010; const int bit=100000000; const int bn=65; int c[]={6,2,5,5,4, 5,6,3,7,6}; int d[maxn][bn]; void Add(int a,int b) { int p=0,i=0; for(i=0;i<bn;i++) { p +=d[a][i]+d[b][i]; d[a][i]=p%bit; p/=bit; } } void print(int i) { if(i==1) {printf("0\n"); return ; } int j=bn-1; while(!d[i][j]) j--; printf("%d",d[i][j--]); while(j>=0) printf("%08d",d[i][j--]); printf("\n"); } int main() { int i,j; d[0][0]=1; for(i=0;i<maxn;i++) { for(j=0;j<10;j++) { if((i || j) && i+c[j]<maxn) Add(i+c[j],i); } } for(i=1;i<maxn;i++) Add(i+1,i); for(i=6;i<maxn;i++) Add(i,0); while(~scanf("%d",&i)) print(i); return 0; }

上一篇:HDOJ 1564
下一篇:2011年福州赛区C题 Bob’s Race 树形DP RMQ

相关文章

关键词: UVA 11375 Mathes

相关评论