P6883 Kroničan 题解

__S08577__ · 2024-08-12 20:51:23 · 题解

题意

P6883

思路

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

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

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

不难推出状态转移方程：

此时，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;
}