P6883 [COCI2016-2017中哪道题的解题思路最独特？

本文共计1159个文字，预计阅读时间需要5分钟。

状态压缩+DP+好题。题目描述：Mislav有+N个玻璃杯，从(1~N)编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子中），使这些杯子中只有+K个有水‘。

状压 DP 好题。

题目描述

Mislav 有 \(N\) 个玻璃杯，从 \(1\sim N\) 编号，每个玻璃杯中都有一定的水。你需要通过倒水（将某个杯子中的水倒入另一个杯子），使这些杯子中只有 \(K\) 个有水。

已知将第 \(i\) 号玻璃杯中的水倒入第 \(j\) 号，需要消耗 \(C_{i,j}\) 的代价。Mislav 想知道，经过倒水后满足只有 \(K\) 个（或更少）玻璃杯中有水时，消耗的代价总和的最小值。

\(1\le K\le N\le 20\)。

大体思路

由于每个水杯只有有水和没水两个状态，并且可以证明，由于一开始所有杯子都有水，操作过程中有水的杯子 \(i\) 不会把水倒到没水的杯子 \(j\)。这是因为如果 \(j\) 不倒出，\(i\to j\) 不会使得有水的杯子数减少；如果 \(j\) 最终倒出，应该在 \(j\) 变成空杯子前进行操作。

所以，本题可以使用状压 DP 进行计算。将 \(N\) 个杯子有无水的状态用 \(N\) 位二进制数 \(S\) 表示，\(f_S\) 表示状态为 \(S\) 时的最小代价。初始 \(f_{111...1}=0\)，其余 \(f=\infty\)。

转移时，从大到小枚举 \(S\)，每次取 \(S\) 的二进制为 \(1\) 的位置 \(p,k\)，满足 \(p\neq k\)，则 \(p\) 号杯子为空的状态可能是由 \(S\) 转移过去，将 \(p\) 倒入 \(k\) 中。