AT_abc432_f 题解

· · 题解

状压 DP。恶心点在于还要还原方案 /tuu 而且码量不小。

显然要先把所有糖果的数量总和算出来，不是 n 的倍数直接无解。否则算出平均值。

首先我们会发现一个特别，啊，显然的性质，就是一次糖果的传递，比如说 x 给 y 多少颗糖，经过这次操作后 x 和 y 这两个人之中一定有一个人已经到达了平均值，不排除两人都到的情况。

这个性质可以延伸出另一个性质，那就是说，一颗糖果绝对不会经过一个人的交手。这样说是不是很模糊啊，那我换种方式，就是说一个糖果最多只会拥有过两个主人，不会说 x 给了 y，y 又给了 z，那何必呢，直接让 x 给 z 不就得了。

所以根据这些性质，如果你当前只考虑了一部分的人，这之中必定最多只有一个人糖果数还没达标。

于是这样就可以定义状态，dp_{st,i} 表示当前考虑了 st 这个二进制压缩集合中的人的糖果情况，且还有 i 这位虽然经过过操作但是糖果数还没达标的人。当然了也有全部达标的情况，这个时候我们就让 i 这一位表示成 0，也就是目前考虑过的人中没有人的糖果数还没达标啦！

最终答案就是 dp_{2^n-1,0}。

初始时肯定全赋初值为 \infty。找最初就糖果数达标的作为起始 strt，让 dp_{strt,0} = 0，这就是初值。

接下来考虑转移。

首先枚举 st，特殊转移第二维是 0 的情况——枚举 i，只要 dp_{st,i} > dp_{st,0}，就可以转移 dp_{st,i} = dp_{st,0}，顺便记录路径方便后面找方案。

接下来枚举 DP 的第二维 i，这里用的是扩散型，对，上面用的也是扩散型。再枚举一个 j，要新加一个 j 进来，当然 j 一定不能在 st 中或者等于 i。并且还有一点很重要的，你会算出 Di 和 Dj 两个标识符，表示 i 和 j 这两个人距离糖果数达标还需要多少。你必须保证 Di 和 Dj 的正负号是不一样的——不然你很有可能给不起！

之后就是判断了，要是 Di 和 Dj 正好相互补上，就能弄出 DP 转移第二维是 0 的情况，st 就会加上 i 和 j 两个人；如果 Di 的绝对值更小一些，就考虑让 i 达标，让 j 去成全 i，把 i 包含进 st 并让第二维是 j；反之如果 Dj 的绝对值更小一些，久石让 j 达标，让 i 成全 j，把 j 包含到 st 里头，第二维还是 i。在这个转移的过程中，要记得及时记录路径，以及要判断这种转移优不优，别越弄越劣了就行。

这样转移环节就结束了，思维难度不高，但是由于有多种情况，代码还有点儿长。

最后输出答案即可，额外再跑一个 DFS 倒着回来找方案，后序遍历顺序输出方案的具体情况即可。

于是这题就搞完啦！有些小细节需要注意一下，本人补题时调了将近一个小时。

#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
using namespace std;
const int N = (1<<20)+5;
const int Inf = 0x3f3f3f3f;
struct node{int x,y,z;}g[N][30];
int n,a[30],s[N],c[N],sum,strt,dp[N][30];
int read(){
    int 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 DFS_rtans(int x,int y){
    if(x==strt&&y==0)return;
    if(x==-1||y==-1)return;
    auto [p,q,o]=g[x][y];
    if(p==0)DFS_rtans(x,0);
    else{
        if(y==0)DFS_rtans((x^(1<<p-1)^(1<<q-1)),p);
        else if(y==q)DFS_rtans(x^(1<<p-1),p);
        else DFS_rtans(x^(1<<q-1),p);
        if(o>0)cout<<p<<" "<<q<<" "<<o<<"\n";
        else cout<<q<<" "<<p<<" "<<-o<<"\n";
    }return;
}
int main(){
    n=read();
    for(int i=1;i<=n;i++)
        a[i]=read(),sum+=a[i];
    if(sum%n!=0){cout<<"-1\n";return 0;}sum/=n;
    for(int st=0;st<(1<<n);st++)
        for(int i=1;i<=n;i++)
            if((st>>i-1)&1)s[st]+=a[i],c[st]++;
    for(int i=1;i<=n;i++)
        if(a[i]==sum)strt|=(1<<i-1);
    memset(dp,0x3f,sizeof(dp));dp[strt][0]=0;
    for(int st=0;st<(1<<n);st++)
        for(int i=0;i<=n;i++)g[st][i]={-1,-1,-1};
    for(int st=0;st<(1<<n);st++){
        if(dp[st][0]!=Inf)for(int i=1;i<=n;i++)
            if(!((st>>i-1)&1)&&dp[st][0]<dp[st][i])
                dp[st][i]=dp[st][0],g[st][i].x=0;
        for(int i=1;i<=n;i++){
            if(dp[st][i]==Inf)continue;
            for(int j=1;j<=n;j++){
                int di=s[st|(1<<i-1)]-c[st|(1<<i-1)]*sum;
                int dj=a[j]-sum,ds=min(abs(di),abs(dj));
                if(((st>>j-1)&1)||((di<0)==(dj<0)))continue;
                if(ds==abs(di)&&ds==abs(dj)){
                    if(dp[st][i]+1<dp[st|(1<<i-1)|(1<<j-1)][0])
                        dp[st|(1<<i-1)|(1<<j-1)][0]=dp[st][i]+1,
                        g[st|(1<<i-1)|(1<<j-1)][0]={i,j,di};
                }else if(ds==abs(di)){
                    if(dp[st][i]+1<dp[st|(1<<i-1)][j])
                        dp[st|(1<<i-1)][j]=dp[st][i]+1,
                        g[st|(1<<i-1)][j]={i,j,di};
                }else if(ds==abs(dj)){
                    if(dp[st][i]+1<dp[st|(1<<j-1)][i])
                        dp[st|(1<<j-1)][i]=dp[st][i]+1,
                        g[st|(1<<j-1)][i]={i,j,-dj};
                }else;
            }
        }
    }cout<<dp[(1<<n)-1][0]<<"\n";
    DFS_rtans((1<<n)-1,0);
    return 0;
}

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