题解 P6883 【[COCI2016-2017#3]Kroničan】
y0y68
·
·
题解
我又来刷水题水贡献了
状压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。
### 四、计算答案
枚举出所有二进制位是 $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