[HDU] XHXJ's LIS

Author            : Dipu Kumar Mohanto 
                    CSE, Batch - 6
                    BRUR.
Problem Statement : XHXJ's LIS
Source            : HDU Online Judge 
Category          : Dynamic Programing
Algorithm         : Digit DP
Verdict           : Accepted

LIS on digit dp 

#include "iostream"
#include "algorithm"
#include "cstring"
 
using namespace std;
 
#define ll          long long
 
inline int setbit(int mask, int pos)                { return mask |= (1 << pos); }
inline int resetbit(int mask, int pos)              { return mask &= ~(1 << pos); }
inline int togglebit(int mask, int pos)             { return mask ^= (1 << pos); }
inline bool checkbit(int mask, int pos)             { return (bool)(mask & (1 << pos)); }
inline int countSetBit(int mask)                    { return __builtin_popcount(mask); }
 
int nxt[(1<<10) + 5][12];
 
inline int setForLIS(int mask, int digit)
{
      if (mask == 0 && digit == 0) return 0;
      for (int i = digit; i <= 9; i++)
      {
            if (checkbit(mask, i))
            {
                   //mask = togglebit(mask, i);
                   //mask = togglebit(mask, digit);
                  mask = resetbit(mask, i);
                  mask = setbit(mask, digit);
                  return mask;
            }
      }
      //mask = togglebit(mask, digit);
      mask = setbit(mask, digit);
      return mask;
}
 
inline void preCalcForLIS()
{
      for (int mask = 0; mask < (1 << 10); mask++)
      {
            for (int digit = 0; digit <= 9; digit++)
            {
                  nxt[mask][digit] = setForLIS(mask, digit);
            }
      }
}
 
ll dp[20][(1<<10)+5][11]; // dp[ position ][ mask ][ size of LIS ]
bool memoize[20][(1<<10)+5][11];
 
int a[22];
 
inline ll solveDigitDP(int pos, int mask = 0, int k = 0, bool flag = 1, bool take = 0)
{
      if (pos < 0)
      {
            return countSetBit(mask) == k;
      }
      ll &ret = dp[pos][mask][k];
      bool &mem = memoize[pos][mask][k];
      if (!flag && take && mem) return ret;
      int loop = 9;
      if (flag) loop = a[pos];
      ll sum = 0;
      for (int i = 0; i <= loop; i++)
      {
            if (!take && i == 0) sum += solveDigitDP(pos-1, 0, k, 0, 0);
            else sum += solveDigitDP(pos-1, nxt[mask][i], k, flag & i == a[pos], 1);
      }
      if (!flag && take) mem = 1, ret = sum;
      return sum;
}
 
inline ll solve(ll x, int k)
{
      int len = 0;
      while (x)
      {
            a[len++] = x % 10;
            x /= 10;
      }
      return solveDigitDP(len-1, 0, k, 1);
}
 
int main()
{
      preCalcForLIS();
      memset(memoize, 0, sizeof memoize);
      int tc;
      cin >> tc;
      for (int tcase = 1; tcase <= tc; tcase++)
      {
            ll num1, num2;
            int k;
            cin >> num1 >> num2 >> k;
            if (num1 > num2) swap(num1, num2);
            ll ans = solve(num2, k) - solve(num1-1, k);
            cout << "Case #" << tcase << ": " << ans << "\n";
      }
}