作者推荐
【数位dp】【动态规划】【状态压缩】【推荐】1012. 至少有 1 位重复的数字
本文涉及知识点
状态压缩
LeetCode1815 得到新鲜甜甜圈的最多组数
有一个甜甜圈商店，每批次都烤 batchSize 个甜甜圈。这个店铺有个规则，就是在烤一批新的甜甜圈时，之前 所有 甜甜圈都必须已经全部销售完毕。给你一个整数 batchSize 和一个整数数组 groups ，数组中的每个整数都代表一批前来购买甜甜圈的顾客，其中 groups[i] 表示这一批顾客的人数。每一位顾客都恰好只要一个甜甜圈。
当有一批顾客来到商店时，他们所有人都必须在下一批顾客来之前购买完甜甜圈。如果一批顾客中第一位顾客得到的甜甜圈不是上一组剩下的，那么这一组人都会很开心。
你可以随意安排每批顾客到来的顺序。请你返回在此前提下，最多 有多少组人会感到开心。
示例 1：
输入：batchSize = 3, groups = [1,2,3,4,5,6]
输出：4
解释：你可以将这些批次的顾客顺序安排为 [6,2,4,5,1,3] 。那么第 1，2，4，6 组都会感到开心。
示例 2：
输入：batchSize = 4, groups = [1,3,2,5,2,2,1,6]
输出：4
提示：
1 <= batchSize <= 9
1 <= groups.length <= 30
1 <= groups[i] <= 109
动态规划
本顾客之前的顾客买的甜甜圈之和 % batchSize 为0，则幸福。
动态规划的状态
groups全部%batchSize，cnt记录为0到batchSize-1的数量。为0的全部放到最前面。 调整为0的顾客，不会议影响其他顾客的幸福度。
极端情况下：8种顾客，6种3位，2种3位。 共有56*16 = 250000。
dp[mask] 记录最大幸福度。
动态规划的转移方程
枚举各类没有售卖完的客人。
动态规划的初始值
全部为0
动态规划的填表顺序
前置条件转移后置条件,mask从0到大。
动态规划的返回值
cnt[0]+dp.back()
代码
核心代码
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); } }
2023年2月版
class Solution {
public:
int maxHappyGroups(int batchSize, vector& groups) {
vector nums(batchSize);
for (const int& group : groups)
{
nums[group%batchSize]++;
}
m_vUnit.push_back(1);
for (int i = 1; i < batchSize; i++)
{
m_vUnit.push_back(m_vUnit.back()*(nums[i] + 1));
}
m_iMaskNum = m_vUnit.back();
vector<vector> vMaskVector(m_iMaskNum);
vector vMaskTotalNum(m_iMaskNum);
for (int i = 0; i < m_iMaskNum; i++)
{
vector vNum(batchSize - 1);
int iNeedNum = 0;
int mask = i;
for (int j = 0; j < batchSize - 1; j++)
{
if (j + 1 < m_vUnit.size())
{
vNum[j] = mask % m_vUnit[j + 1]/m_vUnit[j];
}
else
{
vNum[j] = mask/m_vUnit[j];
}
iNeedNum += (j + 1)*vNum[j];
}
vMaskVector[i] = vNum;
vMaskTotalNum[i] = iNeedNum;
}
vector vMaskMaxHappy(m_iMaskNum);
for (int mask = 0; mask < m_iMaskNum; mask++)
{
const auto& v = vMaskVector[mask];
for (int j = 0; j < v.size(); j++)
{
if (v[j] < nums[j + 1])
{
int& newHappy = vMaskMaxHappy[mask + m_vUnit[j]];
newHappy = max(newHappy, vMaskMaxHappy[mask] + (0 == vMaskTotalNum[mask] % batchSize));
}
}
}
return vMaskMaxHappy[m_iMaskNum - 1] + nums[0];
}
vector m_vUnit;
int m_iMaskNum;
};
