[COCI2016-2017#3] Kroničan 解题记录

题意简述

有 $N$ 个装有水的杯子，你需要通过从一个杯子向另一个杯子倒水，使这些杯子里面至多有 $K$ 个有水，从杯子 $i$ 往杯子 $j$ 倒水的代价是 $C_{i,j}$。

题目分析

数据范围：$1\le N\le 20$，一眼状压。
设 $d{p}_S$ 表示当前装有水的杯子集合为 $S$，每次枚举从杯子 $k\in [1,n]$ 向杯子 $j\in [1,n]$倒水。因为一开始所有杯子都有水，越到后面水越少，所以考虑倒序转移，即从 $2^n-1$ 向 $1$ 转移。
状态转移方程：
$$d{p}_{S⨁j}\leftarrow \underset{k=1}{\overset{n}{\min }}d{p}_S+C_{j,k}$$
对于最后统计答案，我们可以用 __builtin_popcount() 函数（我这里是手写的），对于二进制中 $1$ 的个数小于等于 $K$ 的更新。

AC Code

#include<bits/stdc++.h>
#define arrout(a,n) rep(i,1,n)std::cout<<a[i]<<" "
#define arrin(a,n) rep(i,1,n)std::cin>>a[i]
#define rep(i,x,n) for(int i=x;i<=n;i++)
#define dep(i,x,n) for(int i=x;i>=n;i--)
#define erg(i,x) for(int i=head[x];i;i=e[i].nex)
#define dbg(x) std::cout<<#x<<":"<<x<<" "
#define mem(a,x) memset(a,x,sizeof a)
#define all(x) x.begin(),x.end()
#define arrall(a,n) a+1,a+1+n
#define PII std::pair<int,int>
#define m_p std::make_pair
#define u_b upper_bound
#define l_b lower_bound
#define p_b push_back
#define CD const double
#define CI const int
#define int long long
#define il inline
#define ss second
#define ff first
#define itn int
CI N=25;
int n,K,ans=LLONG_MAX,c[N][N],dp[(1<<N-5)+5];
int calc(int x){
    int cnt=0;
    rep(i,0,20){
        if((x>>i)&1){
            cnt++;
        }
    }
    return cnt;
}
signed main() {
    std::cin>>n>>K;
    rep(i,1,n) {
        rep(j,1,n) {
            std::cin>>c[i][j];
        }
    }
    mem(dp,0x3f);
    dp[(1<<n)-1]=0;
    dep(i,(1<<n)-1,1) {
        rep(j,1,n) {
            if((i>>j-1)&1){
                continue;
            }
            rep(k,1,n) {
                if(!((i>>k-1)&1)) {
                    continue;
                }
                dp[i]=std::min(dp[i],dp[i|(1<<j-1)]+c[j][k]);
            }
        }
    }
    rep(i,1,(1<<n)-1) {
        if(calc(i)<=K) {
            ans=std::min(ans,dp[i]);
        }
    }
    std::cout<<ans;
    return 0;
}