UVA11375

递推+大数
分析参见lij白书p110
 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #include<iostream>
 5 using namespace std;
 6 const int maxn=2010;
 7 
 8 class bign
 9 {
10 public:
11     int date[500];
12     int len;
13     bign(){memset(date,0,sizeof(date));len=1;}
14     void operator =(const int &x)
15     {
16         int temp=x;
17         while(temp)
18         {
19             date[len++]=temp%10;
20             temp/=10;
21         }
22     }
23     bign operator + (const bign& a)
24     {
25         bign temp;
26         temp.len=max(len,a.len);
27         for(int i=1;i<=temp.len;i++)
28         {
29             temp.date[i]+=date[i]+a.date[i];
30             if(temp.date[i]>=10)
31             {
32                 temp.date[i+1]=temp.date[i+1]+temp.date[i]/10;
33                 temp.date[i]%=10;
34                 if(i==temp.len) temp.len++;
35             }
36         }
37         return temp;
38     }
39     bign operator +=(const bign &a)
40     {
41         *this=*this+a;
42         return *this;
43     }
44      bign operator +=(const int &a)
45     {
46         *this=*this+a;
47         return *this;
48     }
49     bign operator+ (const int& a)
50     {
51         bign temp;
52         temp=a;
53         temp=*this+temp;
54         return temp;
55     }
56     friend ostream& operator << ( ostream & out,const bign& ans)
57     {
58         int i=ans.len;
59         while(ans.date[i]==0&&i>=1) i--;
60         if(i!=0)
61             for(;i>=1;i--) out<<ans.date[i];
62         else out<<"0";
63         return out;
64     }
65 };
66 bign ans[maxn],d[maxn];
67 int c[]={6,2,5,5,4,5,6,3,7,6};
68 int main()
69 {
70     d[0]=1;
71     for(int i=0;i<maxn;i++)
72         for(int j=0;j<10;j++)
73         if(!(i==0&&j==0)&&c[j]+i<maxn)
74             d[c[j]+i]+=d[i];
75     ans[0]=0;
76     for(int i=1;i<maxn;i++)
77         ans[i]=ans[i-1]+d[i];
78     for(int i=6;i<maxn;i++)
79         ans[i]+=1;
80     int n;
81     while(cin>>n)
82         cout<<ans[n]<<endl;
83     return 0;
84 }