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 倒着回来找方案，后序遍历顺序输出方案的具体情况即可。

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

CPP

#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;
}

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

文章操作

相关推荐

评论

AT_abc432_f 题解