蒲城做网站,河北工程大学网站开发成本,怎样在国外网站上做宣传,网站建设坂田1.题目描述#xff1a;点击打开链接
2.解题思路#xff1a;本题利用递推关系解决。首先可以把“已经使用过的火柴数i”看做状态#xff0c;可以得到一个图#xff0c;从前往后每添加一个数字x#xff0c;就从状态i转移到了ic[x]#xff0c;其中c[x]代表数字x需要的火柴数…1.题目描述点击打开链接
2.解题思路本题利用递推关系解决。首先可以把“已经使用过的火柴数i”看做状态可以得到一个图从前往后每添加一个数字x就从状态i转移到了ic[x]其中c[x]代表数字x需要的火柴数。当i0时不允许使用数字0当n≥6给答案单独加上1代表整数0。令d(i)表示从结点0到结点i的路径条数则答案为f(n)d(1)d(2)...d(n)。
程序实现时我们可以按照从小到大的顺序用d(i)更新所有的d(ic[j])j取遍数字0~9。由于结果非常大 需要使用高精度模板存储结果。
3.代码 #define _CRT_SECURE_NO_WARNINGS #includeiostream#includealgorithm#includestring#includesstream#includeset#includevector#includestack#includemap#includequeue#includedeque#includecstdlib#includecstdio#includecstring#includecmath#includectime#includefunctionalusing namespace std; typedef long long ll;typedef unsigned long long ull;typedef pairint, int P;typedef pairlong long, long long PL;#define me(s) memset(s,0,sizeof(s))#define For(i,n) for(int i0;i(n);i) #define N 200010int n;int c[] { 6, 2, 5, 5, 4, 5, 6, 3, 7, 6 };struct Node{ int p[500]; int len;Node(){me(p); len 0;}Node(int a){p[0] a;len 1;}Node operator (const Nodea)const{Node b;b.len max(len, a.len);For(i, b.len){b.p[i] p[i] a.p[i];b.p[i 1] b.p[i] / 10;b.p[i] % 10;} if (b.p[b.len] 0)b.len; return b;} void out(){ if (!len)puts(0); else{ for (int i len - 1; i 0; i--) printf(%d, p[i]); puts();}}}d[N]; void init(){d[0].p[0] 1;d[0].len 1; For(i, 2001){For(j,10) if (i c[j] 2001 !(i 0 j 0))//ij0时不允许转移d[i c[j]] d[i c[j]] d[i];}d[6] d[6] Node(1); for (int i 2; i 2001; i)d[i] d[i] d[i - 1]; }int main(){ //freopen(t.txt, r, stdin);init(); while (cin n){d[n].out();} return 0;}
