SRM526 Div2 Hard

1000
メモ化する。
memo[桁数][4の数][7の数][まだ一致しているか]

view plainprint?

1. const int L = 11;  
2.   
3. lli memo[L][L][L][2];  
4. string s;  
5.   
6. lli rec(int len, int _4, int _7, bool small)  
7. {  
8.   if (len == s.size()) return abs(_4 - _7);  
9.   if (memo[len][_4][_7][small] != -1) return memo[len][_4][_7][small];  
10.   
11.   lli sum = 0;  
12.    
13.   int begin, end;  
14.   if (small) {  
15.     begin = 0, end = 9;  
16.   } else {  
17.     begin = 0, end = s[len] - '0';  
18.   }  
19.   
20.   for (int i = begin; i <= end; ++i) {  
21.     sum += rec(len + 1, _4 + (i == 4), _7 + (i == 7), small || i < s[len] - '0');  
22.   }  
23.   
24.   return memo[len][_4][_7][small] = sum;  
25. }  
26.   
27. class SumOfLuckiness {  
28. public:  
29.   long long theSum(int A, int B)  
30.   {     
31.     char buff[L];  
32.   
33.     fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);  
34.     sprintf(buff, "%d", A - 1);  
35.     s = string(buff);  
36.     lli a = rec(0, 0, 0, false);  
37.   
38.     fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);  
39.     sprintf(buff, "%d", B);  
40.     s = string(buff);  
41.     lli b = rec(0, 0, 0, false);  
42.   
43.     return b - a;  
44.   }  
45. };  

const int L = 11;

lli memo[L][L][L][2];
string s;

lli rec(int len, int _4, int _7, bool small)
{
  if (len == s.size()) return abs(_4 - _7);
  if (memo[len][_4][_7][small] != -1) return memo[len][_4][_7][small];

  lli sum = 0;
 
  int begin, end;
  if (small) {
    begin = 0, end = 9;
  } else {
    begin = 0, end = s[len] - '0';
  }

  for (int i = begin; i <= end; ++i) {
    sum += rec(len + 1, _4 + (i == 4), _7 + (i == 7), small || i < s[len] - '0');
  }

  return memo[len][_4][_7][small] = sum;
}

class SumOfLuckiness {
public:
  long long theSum(int A, int B)
  {   
    char buff[L];

    fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);
    sprintf(buff, "%d", A - 1);
    s = string(buff);
    lli a = rec(0, 0, 0, false);

    fill(&memo[0][0][0][0], &memo[L - 1][L - 1][L - 1][2], -1);
    sprintf(buff, "%d", B);
    s = string(buff);
    lli b = rec(0, 0, 0, false);

    return b - a;
  }
};