Advertisement
Rana_093

DigitDPTemplate

Nov 3rd, 2018
147
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 KB | None | 0 0
  1. ///http://www.spoj.com/problems/CPCRC1C/
  2. #include<bits/stdc++.h>
  3.  
  4. using namespace std;
  5.  
  6. #define ll long long int
  7. #define db(x) cout<<#x<<" -> "<<x<<endl
  8.  
  9. vector<int>digit;
  10. const int mx = 83;
  11. int sz = -1;
  12. ll dp[10][2][2][83];
  13.  
  14. void init(ll n){
  15.     digit.clear();
  16.     while(n){
  17.         digit.push_back(n%10);
  18.         n/=10;
  19.     }
  20.     reverse(digit.begin(),digit.end());
  21.     sz = digit.size();
  22.     return ;
  23. }
  24.  
  25. ll recur(int pos,bool small,bool start,int sum){
  26.     if(pos==sz){
  27.         return sum;
  28.     }
  29.     if(dp[pos][small][start][sum]!=-1){
  30.         return dp[pos][small][start][sum];
  31.     }
  32.     int lim = (small)?9:digit[pos];
  33.     ll ret = 0;
  34.     if(! start){ ///
  35.         for(int i=0; i<=lim; i++){
  36.             ret+= recur(pos+1, small | i<digit[pos] , 0, sum+i);
  37.         }
  38.     }
  39.     else{
  40.         for(int i=1; i<=lim; i++){
  41.             ret+= recur(pos+1, small | i<digit[pos], 0, sum+i);
  42.         }
  43.         ret+= recur(pos+1,1,1,0);
  44.     }
  45.     return dp[pos][small][start][sum]=ret;
  46. }
  47.  
  48.  
  49. ll fuck(ll n){
  50.     if(n==0){
  51.         return 0LL;
  52.     }
  53.     if(n<=9){
  54.         ll temp = n*(n+1)/2;
  55.         return temp;
  56.     }
  57.     init(n);
  58.     memset(dp,-1,sizeof(dp));
  59.     return recur(0,0,1,0);
  60. }
  61.  
  62.  
  63. int main()
  64. {
  65.     ios_base::sync_with_stdio(false);
  66.     cin.tie(0);
  67.     ll n,m;
  68.     while(cin>>n>>m){
  69.         if(n==-1 && m==-1){
  70.             return 0;
  71.         }
  72.         ll f = fuck(n-1);
  73.         ll s = fuck(m);
  74.         ll samia = s-f;
  75.         cout<<samia<<endl;
  76.     }
  77.     return 0;
  78. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement