happy number 中南OJ 1275 数位DP

记录我做的第一个数位DP，听起来好高深，呵呵````

http://122.207.68.93/OnlineJudge/problem.php?cid=2031&pid=7

这个题就是给你a,b。输出[a,b]中间有多少个happy number.

仔细考虑happy number的定义发现，一个18位的数，它的平方和最大会为每位都取9，即9*9*18=1458.

如果我先计算出了1-1500之间的happy number.任给你一个数（大于1500），要判断出它是不是happy number，就把它每位数的平方和算出来，如果该数是个happy number,那么它的平方和值也会是个happy number，反过来也成立。

而怎样判断一个数不是happy number，如果重复算数的平方和的时候，该值重复出现，就证明该循环是死循环了，那么最多1500次就能判断一个数是不是happy number.

比如说2

2*2 = 4

4*4 = 16

1*1+6*6=37

3*3+7*7=58

5*5+8*8=89

8*8+9*9 = 145

1*1+4*4+5*5 = 42

4*4 +2*2 = 20

2*2+0*0 = 4

唉，终于出现循环了，手算很苦逼，这就证明了2不是个happy number.

接下来搞数位拓展，dp[i][j]记录一个从1到i位数中平方和为 j的个数。

比如i =4,dp[4][89]表明从0-9999中平方和为89的有多少个。

感觉没讲清楚，贴代码：

View Code

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <iostream>
 4 using namespace std;
 5 typedef long long int LL;
 6 bool isHappy[1505];
 7 LL dp[20][1505];
 8 void gene()//先把1-9*9*18的happy number算出来
 9 {
10     bool vis[1500];
11     for(int i=1; i<=1500; ++i)
12     {
13         memset(vis,0,sizeof(vis));
14         int sum = i;
15         bool flag = true;
16         while(flag)
17         {
18             int k = sum;
19             sum = 0;
20             while(k != 0)//算出组成该数的每个数字的平方和
21             {
22                 int t = k%10;
23                 k = k/10;
24                 sum += t*t;
25             }
26             if(sum == 1) break;//为1，为happy number
27             if(vis[sum]) flag = false;//该平方和值已经出现过，证明陷入了循环
28             vis[sum] =1;//记录中间出现过的平方和值
29         }
30         if(flag) isHappy[i] = 1;//flag为true,是happy number
31     }
32 }
33 void preSolve()
34 {
35     dp[0][0] = 1;//初始时一位数都没有，平方和为0的个数为1
36     for(int i=1; i<=18; ++i)
37     {
38         for(int k=0; k<=9; ++k)//k要从0-9，不能从1-9
39         {
40             for(int j=0; j<=1500; ++j)
41             {
42                 dp[i][j+k*k] += dp[i-1][j];
43             }
44         }//该循环结束后算出了i位数中平方和为j的有多少个
45     }
46 }
47 LL count(LL x)
48 {
49     int st[20];
50     int cur = 0;
51     while(x!=0)//把x每位分离，放入st栈中（数组模拟栈）
52     {
53         st[cur++] = x%10;
54         x = x/10;
55     }
56     LL ans = 0;//有多少个happy number,初值为0
57     int sum = 0;
58     for(int w = cur-1; w >= 0; --w)
59     {
60         for(int i=0; i<st[w]; ++i)
61         {
62             for(int j=0; j<=1500; ++j)
63             {
64                 if(isHappy[sum+i*i+j])
65                     ans += dp[w][j];
66             }
67         }
68         sum += st[w]*st[w];
69     }
70     //举例说明如何求1-n中有多少个happy number.这里n = 7843
71     //先看最高位，这里为7，计算出从1-6999中有多少个
72     //happy number，然后固定最高位为7，次高位为8，算出7000-7799中有多少个
73     //happy number，再固定78，因为8后面是4，算出7800-7839有多少个happy number
74     //固定784，4后面是3，算出7840-7842中有多少个happy number。最后看7843本身是不是
75     //happy number.这样1-7843中的happy number数就都算出来了。
76     if(isHappy[sum]) ++ans;
77     return ans;
78 }
79 int main()
80 {
81 //    freopen("in.cpp","r",stdin);
82     gene();
83     preSolve();
84     int T;
85     scanf("%d",&T);
86     while(T--)
87     {
88         LL a,b;
89         cin>>a>>b;
90         cout<<count(b)-count(a-1)<<endl;
91     }
92     return 0;
93 }