AT_abc480_f 题解

· · 题解

我的时间复杂度和 M 无关诶，肯定是假的。

？？？怎么过了？

这出题人没力气。

我要飞起来。

我们发现 n 只有 20。一般这种数量级的 n，要么是爆搜要么是状压。考虑到出题人还是有良心的，这是 F，应该是后者。

感觉我的做法最重要的一步是发现一个性质：最优的划分方案，一定可以通过将所有蛋糕排成一行然后和 \ge M 了就切一刀这样的方式构造出来。

这十分的不可思议，以至于我一直认为是假的。但后来我相信它是真的了。

我们可以比较感性地理解一下。没办法这样构造出来的情况只有可能是因为分配关系中出现了“环”（比如两个不同的人人交叉着分到了某两块相同蛋糕的碎片），而在这种情况下，一定能把某些碎块重新拼回一整块，我们可以等量交换这些人手中的碎片以将环解开，将其转变为最开始的链结构。一步步这样变化总能够转变回最初提到的情况，于是就算是证完了。

不过赛时因为找不到明显的 hack 所以还是决定相信自己了。

考虑你得到这个东西之后该怎么做。时刻记住 n 只有 20 诶，结合我们最开始就提到了的状压，令 dp_{st} 表示当前已经排列了 st 这些蛋糕集合的情况下最少的切的刀数。初值 dp_0 = 0，答案是 dp_{2^n-1}，转移的时候枚举新加入的值并根据余数一类求出需要多切几刀即可。非常简单，代码也十分好写。

::::success[code && submission]

#include<bits/stdc++.h>
#define LL long long
#define UInt unsigned int
#define ULL unsigned long long
#define LD long double
#define pii pair<int,int>
#define pLL pair<LL,LL>
#define pDD pair<LD,LD>
#define fr first
#define se second
#define pb push_back
#define isr insert
#define _i128 __int128
using namespace std;
const int N = 25;
const int K = (1<<20)+5;
const LL INF = 1e18+1099;
LL n,m,all,a[N],dp[K];
LL read(){
    LL su=0,pp=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')pp=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){su=su*10+ch-'0';ch=getchar();}
    return su*pp;
}
void upd(LL &x,LL y){x=min(x,y);return;}
int main(){
    n=read(),m=read();
    for(int i=1;i<=n;i++)a[i]=read(),all+=a[i];
    m=all/m;//每人应得
    for(int st=0;st<(1<<n);st++)dp[st]=INF;
    dp[0]=0;//起点
    for(int st=0;st<(1<<n);st++){
        if(dp[st]>=INF)continue;
        LL sum=0;
        for(int i=1;i<=n;i++)
            if(st&(1<<i-1))sum+=a[i];
        sum%=m;
        for(int i=1;i<=n;i++){
            if(st&(1<<i-1))continue;//已被包含
            LL add=0;
            if(sum+a[i]>m){
                add=(a[i]-(m-sum)+m-1)/m;
            }
            upd(dp[st|(1<<i-1)],dp[st]+add);
            //转移时计算切割次数
        }
    }
    cout<<dp[(1<<n)-1]<<"\n";
    return 0;
}

::::

如果本篇题解对你有帮助的话，麻烦你点一个小小的赞，真是太感谢啦！