【动态规划】【 数位dp】2827. 范围中美丽整数的数目

template<class ELE, class ResultType, ELE minEle, ELE maxEle>
class CLowUperr
{
public:
  CLowUperr(int iCustomStatusCount) :m_iCustomStatusCount(iCustomStatusCount)
  {
  }
  void Init(const ELE* pLower, const ELE* pHigh, int iNum)
  {
    m_vPre.assign(4, vector<ResultType>(m_iCustomStatusCount));
    if (iNum <= 0)
    {
      return;
    }
    InitPre(pLower, pHigh);
    iNum--;
    while (iNum--)
    {
      pLower++;
      pHigh++;
      vector<vector<ResultType>> dp(4, vector<ResultType>(m_iCustomStatusCount));
      OnInitDP(dp);
      //处理非边界
      for (auto tmp = minEle; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[0], tmp);
      }
      //处理下边界
      OnEnumOtherBit(dp[1], m_vPre[1], *pLower);
      for (auto tmp = *pLower + 1; tmp <= maxEle; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[1], tmp);
      }
      //处理上边界
      OnEnumOtherBit(dp[2], m_vPre[2], *pHigh);
      for (auto tmp = minEle; tmp < *pHigh; tmp++)
      {
        OnEnumOtherBit(dp[0], m_vPre[2], tmp);
      }
      //处理上下边界
      if (*pLower == *pHigh)
      {
        OnEnumOtherBit(dp[3], m_vPre[3], *pLower);
      }
      else
      {
        OnEnumOtherBit(dp[1], m_vPre[3], *pLower);
        for (auto tmp = *pLower + 1; tmp < *pHigh; tmp++)
        {
          OnEnumOtherBit(dp[0], m_vPre[3], tmp);
        }
        OnEnumOtherBit(dp[2], m_vPre[3], *pHigh);
      }
      m_vPre.swap(dp);
    }
  }
protected:
  const int m_iCustomStatusCount;
  void InitPre(const ELE* const pLower, const ELE* const pHigh)
  {
    for (ELE cur = *pLower; cur <= *pHigh; cur++)
    {
      int iStatus = 0;
      if (*pLower == cur)
      {
        iStatus = *pLower == *pHigh ? 3 : 1;
      }
      else if (*pHigh == cur)
      {
        iStatus = 2;
      }
      OnEnumFirstBit(m_vPre[iStatus], cur);
    }
  }
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue) = 0;
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue) = 0;
  virtual void OnInitDP(vector<vector<ResultType>>& dp)
  {
  }
  vector<vector<ResultType>> m_vPre;
};
class CMy : public CLowUperr<char, int, '0', '9'>
{
public:
  typedef  int ResultType;
  typedef  char ELE;
  CMy(int k) :CLowUperr<char, int, '0', '9'>(400), m_iK(k)
  {
  }
  virtual void OnEnumOtherBit(vector<ResultType>& dp, const vector<ResultType>& vPre, ELE curValue)
  {
    const int index = curValue - '0';
    for (int iPreMask = 0; iPreMask < m_iCustomStatusCount; iPreMask++)
    {
      const int preK = iPreMask % 20;
      const int pre01 = iPreMask / 20 ;
      const int k = (preK*10+index) % m_iK;
      int i01 = (index & 1) ? 1 : -1;
      if ((pre01 + i01 < 0) || (pre01 + i01 >= 20))
      {
        continue;
      }
      const int mask = Mask(pre01+i01-10, k);
      dp[mask] += vPre[iPreMask];
    }
  }
  virtual void OnEnumFirstBit(vector<ResultType>& vPre, const ELE curValue)
  {
    const int index = curValue - '0';
    const int k = index % m_iK;
    int i01 = (index & 1) ? 1 : -1;
    const int mask = Mask(i01,k);
    vPre[mask]++;
  }
  int Result()const
  {
    int iRet = 0;
    for (int status = 0; status < 4; status++)
    {
      iRet += m_vPre[status][200];
    }
    return iRet;
  }
protected:
  int Mask(int i01, int k) {  return (i01 + 10) * 20 + k; }
  const int m_iK;
};
class Solution {
public:
  int numberOfBeautifulIntegers(int low, int high, int iK) {
    string strLow = std::to_string(low);
    string strHigh = std::to_string(high);
    int iRet = 0;
    const int len1 = strLow.length();
    const int len2 = strHigh.length();
    if (len1 == len2)
    {
      return Do(strLow, strHigh, iK);
    }
    iRet += Do(strLow, string(len1, '9'),iK);
    for (int i = len1 + 1; i < len2; i++)
    {
      iRet += Do("1" + string(i - 1, '0'), string(i, '9'), iK);
    }
    iRet += Do("1" + string(len2 - 1, '0'), strHigh, iK);
    return iRet;
  }
  int Do(const string strLow,const string& strHigh,int k)
  {
    CMy my(k);
    my.Init(strLow.data(), strHigh.data(), strLow.length());
    return my.Result();
  }
};

template<class T, class T2>
void Assert(const T& t1, const T2& t2)
{
  assert(t1 == t2);
}
template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    Assert(v1[i], v2[i]);
  }
}
int main()
{
  
  int low = 1, high = 10, k = 1;
  {
    low = 1, high = 10, k = 1;
    auto res = Solution().numberOfBeautifulIntegers(low, high, k);
    Assert(1, res);
  }
  {
    low = 5, high = 5, k = 2;
    auto res = Solution().numberOfBeautifulIntegers(low, high, k);
    Assert(0, res);
  }
  {
    low = 10, high = 20, k = 3;
    auto res = Solution().numberOfBeautifulIntegers(low, high, k);
    Assert(2, res);
  }
  
}