1815. 得到新鲜甜甜圈的最多组数 状态压缩

1815. 得到新鲜甜甜圈的最多组数

有一个甜甜圈商店，每批次都烤 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] <= 1e9

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/maximum-number-of-groups-getting-fresh-donuts
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

做题结果

失败，怎么弄都超时，就好头疼，想状态压缩，但是不太方便，数字都不一样

方法：状态压缩

这题是以前都没遇到过的不等长状态压缩。什么意思呢？就是比如当前数字最大可以到5，那么对于这一位，它的进制数就是6，满6进一刚好余数0到5，下一位最大数字2，满3进1刚好可以枚举0到2，所以这两位合起来一共有 6*3种可能性，这里枚举一个数字映射：7->[2,1] （2+1*5）。这样就解决了枚举不连续的问题。

第二个问题是，如何做到取其中一位的数字。拿现在的十进制举例：120，要求中间的2，我们可以用 120%100/10,取出中间这位，也就是需要下一位和当前位的基数。所以预处理计算出每个基数的值，特别地，多枚举一位全部的乘积值，防止溢出

具体步骤：

1. 取到所有数字的余数进行统计，获得每个余数对应的个数

2. 计算到达某位取余的基数

3. 二进制枚举每种可能的情况，在通过取余再取整的方式，拿出这一位具体数值，求和

4. 如果前面取到余数为0，后面这位不论取到什么结果都是会开心，所以遇到余数为0的情况，结果要加1个；遇到余数非0的情况，结果不变。枚举当前可以取到数值中的任意一个，他们都可能是最后一个数，取其中的最优结果。

5. 将计算的结果，取最大值累计到答案中。

6. 前面的步骤，可以先不算余数为0的部分。因为余数为0必然开心。余数为0的值直接累计到答案中。

class Solution {
    public int maxHappyGroups(int batchSize, int[] groups) {
        if(batchSize==1) return groups.length;
        int[] mods = new int[batchSize];
        for(int group:groups) mods[group%batchSize]++;
        int []base = new int[batchSize+1];
        base[1]=1;
        for(int i = 2;i<=batchSize;i++){
            base[i]=base[i-1]*(mods[i-1]+1);
        }
        int total = base[batchSize];
        int ans = 0;
        int[] dp = new int[total];
        for(int i = 1; i < total; i++){
            int[] tms = new int[batchSize];
            int sum = 0;
            for(int j = 1; j <batchSize; j++){
                int v  = i%base[j+1]/base[j];
                tms[j]=v;
                sum += v*j;
            }

            for(int j = 1; j < batchSize; j++){
                int v  = i%base[j+1]/base[j];
                if(tms[j]>0){
                    dp[i] = Math.max(dp[i-base[j]]+((sum-j)%batchSize==0?1:0),dp[i]);
                }
            }
            ans = Math.max(ans,dp[i]);
        }
        return ans+mods[0];
    }
}