自动搬运

查看原文

来自洛谷，原作者为

	y0y68 AFO

搬运于2025-08-24 22:24:55，当前版本为作者最后更新于2020-10-25 11:00:44，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

我又来刷水题水贡献了

状压DP入门题。。。

先看数据范围 $1 \le m \le n \le 20$（这里及以下所说的 $m$ 都是题目中的 $k$） 心生疑惑，再看题显然DP。于是就一定是状压DP。

前置知识：位运算

一、设状态

设 $dp[i]$ 为将初始状态（即杯子全都有水）变为状态 $i$ 所需最小代价。

其中若将 $i$ 表示成二进制（如 $5$ 表示为 $101$），第 $i$ 位（这里及以下所说的第几位皆为从右往左）为 $1$，就表示第 $i$ 个杯子没水，$0$ 就表示第 $i$ 个杯子有水。

二、初始化

初始化 $dp$ 无穷大，$dp[0]=0$。

三、转移方程

$dp[i]=\min(dp[i],dp[i \oplus (1<<j)]+c[j+1][k+1])$

其中 $i$ 转成二进制后第 $j+1$ 位是 $1$，第 $k+1$ 位是 $0$。

$\oplus$ 表示按位异或，$i \oplus (1<<j)$ 表示 将 $i$ 的二进制形式中第 $j+1$ 位变成 $0$ 后的数，即第 $j+1$ 个杯子变得有水。当然有水就得倒，倒就要有花费（必须往原来就有水的杯子即第 $k+1$ 个杯子里面倒，不然无法减少有水的杯子数量），于是加上水从第 $j+1$ 倒往第 $k+1$ 个杯子的所需花费。

四、计算答案

枚举出所有二进制位是 $0$ 的个数小于等于 $m$ 的状态，从中取最小值，便是答案。

代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=21;
int n,m,a[N][N],dp[1<<N];
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++)
		for(int j=1;j<=n;j++)
			cin>>a[i][j];
	memset(dp,0x3f,sizeof dp);
	dp[0]=0;
	for(register int i=1;i<(1<<n);i++)
		for(register int j=0;j<n;j++)
			if(i&(1<<j))//判断第j+1位是不是1
				for(register int k=0;k<n;k++)
					if(!(i&(1<<k)))//判断第k+1位是不是0
                    				dp[i]=min(dp[i],dp[i^(1<<j)]+a[j+1][k+1]);
	int ans=-1u/2;//即2的31次方-1
	for(register int i=0;i<(1<<n);i++){
		int cnt=0;
		for(register int j=0;j<n;j++)
			if(!(i&(1<<j)))cnt++;//统计有几位是0
		if(cnt<=m)ans=min(ans,dp[i]);
	}
	cout<<ans<<endl;
	return 0;
}

点个赞再走吧o(￣▽￣)o