题解：AT_abc480_f [ABC480F] Cake Cutting

ysw_2029 · 2026-10-19 07:29:33 · 题解

状压好题。

考虑将蛋糕排成一排，会发现我们至多切 m-1 次蛋糕。而让切蛋糕的次数最小就是让人之间的分割线与蛋糕之间的分割线重叠的次数最多。

上面的蓝线是人之间的分割线，下面的红色矩形是若干个蛋糕。如果让两条分割线重叠了，那么这个位置就不需要再进行切割了。

那么这两条分割线重叠相当于什么呢？发现人之间的分割线间隔相等，那么重叠就说明前面的蛋糕大小之和为每个人分到的大小（也就是 \frac{S}{M}）的倍数。而 N 只有 20，因此就可以想到状压。

那么接下来就好想多了，直接设 f_i 表示状态 i 至多重叠几次，然后先从状态 i 中去掉一个蛋糕找到之前的最大的次数，再判断状态 i 中的蛋糕大小之和是否为 \frac{S}{M} 的倍数即可。时间复杂度 n2^n。

:::success[AC code]

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,m,s,a[102],k,f[100+(1<<20)];
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i],s+=a[i];
    k=s/m,f[0]=0;
    for(int i=1;i<(1<<n);i++)
    {
        for(int j=1;j<=n;j++)if(i&(1<<(j-1)))
            f[i]=max(f[i],f[i^(1<<(j-1))]);
        int sum=0;
        for(int j=1;j<=n;j++)if(i&(1<<(j-1)))sum+=a[j];
        if(sum%k==0)f[i]++;
    }
    cout<<m-f[(1<<n)-1];
    return 0;
}

:::