本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-08-12 20:51:23

题意

P6883

思路

观察数据范围，考虑状压DP。

设 $dp_i$ 为状态为 $i$ 时，消耗的代价总和的最小值。当 $i$ 的第 $j$ 位为 $0$ 时，则第 $j$ 个杯子有水，反之没水。

初始化，$dp_0=0$。显然，当所有杯子都有水时，不需要操作，所以代价为 $0$。

不难推出状态转移方程： $$dp_i=\min(dp_i,dp_{i\oplus(1<<j)+c_{j+1,k+1}}) $$

此时，$i$ 的第 $j$ 位为 $1$，第 $k$ 位为 $0$。

此时做的操作为将第 $k$ 个杯子的水倒进第 $j$ 个杯子里。

其中，$i\oplus(1<<j)$ 时将 $i$ 的第 $j+1$ 位变成 $0$，既然倒水了，就要加上代价。

最后，我们枚举所有的状态，当有水的杯子数($0$ 的数量)比 $k$ 小，记录并更新最小值，输出最小值即可。

代码

signed main(){
    
  freopen("b.in","r",stdin);
  freopen("b.out","w",stdout);
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++) cin>>c[i][j];
    }
    memset(dp,0x3f,sizeof(dp));
    dp[0]=0;
    for(int i=1;i<(1<<n);i++){
        for(int j=0;j<n;j++){
            if(i&(1<<j)){
                for(int k=0;k<n;k++){
                    if(!(i&(1<<k))){
                        dp[i]=min(dp[i],dp[i^(1<<j)]+c[j+1][k+1]);
                    }
                }
            }
        }
    }
    for(int i=0;i<(1<<n);i++){
        int cnt=0;
        for(int j=0;j<n;j++){
            if((i&(1<<j))==0) cnt++;
        }
       \/\/ cout<<i<<' '<<dp[i]<<' '<< cnt<<'\n';
        if(cnt<=m) minn=min(minn,dp[i]);
    }
    cout<<minn;
    
    return 0;
}