|
题意：
? ? ? 给你n根火柴，问你能组成多少种数字，比如3根可以组成1或者7，组成的数字中不能有前导0，
思路： ? ? ? 我们开一个数组，d[i]记录用i跟火柴可以组成多少种数字，则更新状态是这样的 d[i+c[j]] += d[i],c[j]就是组成数字j要用的火柴数，这样跟新相当于是在模拟写数字，但是有一点就是不能以0开头，左后当火柴数大于等于6的时候就可以在总答案上+1，表示可以构成一个单独的0（因为之前没有0开头的，所以要+1补回来），最后答案就是 Ans[n] = d[1] + d[2] + d[3] + .... + d[n],因为火柴可以不全部用完，还有就是数据比较大，要用大数模拟，这个就不解释了。 #include<stdio.h> #include<string.h> #define N 2000 + 5 int d[N][1000]; int Ans[N][1000]; void solve() { ? ?int i,j; ? ?int c[] = {6,2,5,4,6,3,7,6}; ? ?memset(d,sizeof(d)); ? ?d[0][1] = 1; ? ?for(i = 0 ;i <= 2000 ;i ++) ? ?for(j = 0 ;j <= 9 ;j ++) ? ?{ ? ? ? if(!(i==0&&j==0) && i+c[j] <= 2000) ? ? ? { ? ? ? ? ?//d[i+c[j]] += d[i]; ? ? ? ? ?for(int k = 1 ;k <= 888 ;k ++) ? ? ? ? ?d[i+c[j]][k] += d[i][k]; ? ? ? ? ?for(int k = 1 ;k <= 888 ;k ++) ? ? ? ? ?{ ? ? ? ? ? ? d[i+c[j]][k+1] += d[i+c[j]][k] / 10; ? ? ? ? ? ? d[i+c[j]][k] %= 10; ? ? ? ? ?} ? ? ? } ? ?} ? ? ? ?for(i = 1 ;i <= 2000 ;i ++) ? ?{ ? ? ? if(i == 1) ? ? ? { ? ? ? ? ?for(j = 1 ;j <= 888 ;j ++) ? ? ? ? ?Ans[i][j] = d[i][j]; ? ? ? ? ?continue; ? ? ? } ? ? ? //Ans[i] = Ans[i-1] + d[i]; ? ? ? for(j = 1 ;j <= 888 ;j ++) ? ? ? Ans[i][j] = Ans[i-1][j] + d[i][j]; ? ? ? for(j = 1 ;j <= 888 ;j ++) ? ? ? { ? ? ? ? ?Ans[i][j+1] += Ans[i][j] / 10; ? ? ? ? ?Ans[i][j] %= 10; ? ? ? } ? ?} ? ? ?? ? ?for(i = 6 ;i <= 2000 ;i ++) ? ?{ ? ? ? Ans[i][1] ++; ? ? ? if(Ans[i][1] >= 10) ? ? ? for(int k = 1 ;k <= 888 ;k ++) ? ? ? { ? ? ? ? ?Ans[i][k+1] += Ans[i][k] / 10; ? ? ? ? ?Ans[i][k] %= 10; ? ? ? } ? ?} } int main () { ? ?int n,i,j; ? ?solve(); ? ?while(~scanf("%d",&n)) ? ?{ ? ? ? for(i = 888 ;i >= 1 ;i --) ? ? ? if(Ans[n][i]) break; ? ? ? if(i == 0) ? ? ? { ? ? ? ? ?printf("0n"); ? ? ? ? ?continue; ? ? ? } ? ? ? for(;i >= 1;i --) ? ? ? printf("%d",Ans[n][i]); ? ? ? printf("n"); ? ?} ? ?return 0; } ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ?
（编辑：李大同）
【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!
|
