【动态规划】【状态压缩】【C++算法】1815 得到新鲜甜甜圈的最多组数

class CMask
{
public:
  void Add(int iMax)//当前最高位范围[0,iMax]
  {
    m_vUint.push_back(m_iMaskCount);
    m_vMax.emplace_back(iMax);
    m_iMaskCount *= (iMax + 1);
  }
  vector<int> FromMask(int iMask)const
  {
    vector<int> vNums;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      vNums.emplace_back(iMask % (m_vMax[i] + 1));
      iMask /= (m_vMax[i] + 1);
    }
    return vNums;
  }
  int GetUnit(int iBit)const
  {
    return m_vUint[iBit];
  }
  int ToMask(const vector<int>& vNums, int iMul = 1)const
  {
    int iMask = 0;
    int iUnit = 1;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      iMask += iUnit * min(m_vMax[i], vNums[i] * iMul);
      iUnit *= (m_vMax[i] + 1);
    }
    return iMask;
  }
  int MaskSubVector(int iMask, const vector<int>& vNums, const int iMul = 1)const
  {
    int iNewMask = 0;
    int iUnit = 1;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      int cur = iMask % (m_vMax[i] + 1);
      cur -= vNums[i] * iMul;
      cur = max(0, cur);
      iNewMask += iUnit * cur;
      iMask /= (m_vMax[i] + 1);
      iUnit *= (m_vMax[i] + 1);
    }
    return iNewMask;
  }
  int NeedGroupCount(const vector<int>& need, const vector<int>& has)const
  {
    int iMax = 0;
    for (int i = 0; i < m_vMax.size(); i++)
    {
      if (has[i] <= 0)
      {
        continue;
      }
      iMax = max(iMax, need[i] / has[i] + (0 != need[i] % has[i]));
    }
    return iMax;
  }
public:
  int MaskCount()const
  {
    return m_iMaskCount;
  }
  int BitCount()const
  {
    return m_vMax.size();
  }
protected:
  int m_iMaskCount = 1;
  vector<int> m_vMax;
  vector<int> m_vUint;
};
class Solution {
public:
  int maxHappyGroups(int batchSize, vector<int>& groups) {
    vector<int> cnt(batchSize);
    for (const auto& n : groups)
    {
      cnt[n % batchSize]++;
    }
    int iRet = cnt[0];
    CMask mask;
    for (int i = 1; i < batchSize; i++)
    {
      mask.Add(cnt[i]);
    }
    vector<int> dp(mask.MaskCount());
    for (int i = 0; i < mask.MaskCount(); i++)
    {
      vector<int> v = mask.FromMask(i);
      int sum = 0;
      for (int j = 0; j < v.size(); j++)
      {
        sum += (j + 1) * v[j];
      }
      sum = sum % batchSize;
      for (int j = 0; j < v.size(); j++)
      {
        if (v[j] < cnt[j + 1])
        {
          const int i1 = i + mask.GetUnit(j);
          dp[i1] = max(dp[i1], dp[i] + (0 == sum));
        }
      }
    }
    return iRet + dp.back();
  }
};

template<class T>
void Assert(const T& t1, const T& 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 batchSize;
  vector<int> groups;
  {
    Solution sln;
    batchSize = 3, groups = { 1, 2, 3, 4, 5, 6 };
    auto res = sln.maxHappyGroups(batchSize, groups);
    Assert(res, 4);
  }
  
  {
    Solution sln;
    batchSize = 3, groups = { 1, 2, 3, 4, 5, 6 };
    auto res = sln.maxHappyGroups(batchSize, groups);
    Assert(res, 4);
  }
}