解答传播游戏

题目

题目描述

编号为1至n的n个人正在开展一项传递物品的游戏。游戏规定如下：初始时物品可在任一参与者手中持有，并可将该物品传送给其他参与者中的任何一个；随后每位参与者只能将该物品传送给尚未持有过此物的人。这意味着每个参与者只能持有该物一次，并且每一次转移都伴随一定的成本；此外，在转移过程中各个参与者的代价值之间并无关联。我们的目标是确定当该物经过所有参与者后所需最小总代价值是多少。

输入格式

其中第一行为n名参与者的信息（满足2\leq n\leq 16）。具体表现为一个n\times n的矩阵，在(i+1)行i列的位置上设置值为-1以避免自身传递的情况；其余所有数值均为正整数且不超过10,000）。

输出格式

一个数，为最小的代价总和。

样例

输入样例：

    2
    -1 9794
    2724 –1

输出样例：

    2724

题解

前置芝士

二进制枚举子集

解析

我们能够想到一种基于动态规划的方法来解决此问题。这种状态定义为物品当前归属以及是否被其他人接收。比如，在n=3的情况下，请考虑这样一个场景：我们使用一个四维数组int dp[2][2][2][3]用于记录每