描述
n个人在做传递物品的游戏,编号为1-n。
游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。
即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；求当物品经过所有n个人后，整个过程的总代价是多少。
格式
输入格式
第一行为n,表示共有n个人（16>=n>=2）；以下为n*n的矩阵，第i+1行、第j列表示物品从编号为i的人传递到编号为j的人所花费的代价，特别的有第i+1行、第i列为-1（因为物品不能自己传给自己），其他数据均为正整数(<=10000)。
(对于50%的数据，n<=11)。
输出格式
一个数，为最小的代价总和。
样例1
样例输入1[复制]2-1 97942724 –1样例输出1[复制]2724
限制
所有数据时限为1s
来源
jszx
此题可以直接用记忆化搜索来更加简便，，这里暂时提到的是状态压缩DP;
dp[0][i][j][k]为选择了几个人
dp[1][i][j][k]为最小代价
所以：
dp[1][i][j][k] = min(dp[1][i][j][k], dp[1][i – 1][f][j] + V[j][k]){k 不属于S{已经选了的人}}。
//package ds;import java.util.*;import java.math.*;import java.io.*;public class Main {static Scanner cin = null;static PrintStream cout = null;static final int MAXN = 20;static int INF = 0x3f3f3f3f;static int[][] V = new int[MAXN][MAXN];static int[][][][] dp = new int[2][MAXN][MAXN][MAXN];static int Bit_Count(int val) {//有几个人已经传递过int ret = 0;while (val > 0) {val &= (val – 1);ret++;}return ret;}public static void main(String[] agrs) throws IOException {// System.setIn(new FileInputStream(new File("D:" + File.separator +// "imput.txt")));cin = new Scanner(System.in);cout = new PrintStream(System.out);while (cin.hasNext()) {int n = cin.nextInt();for (int i = 1; i <= n; i++) {for (int j = 1; j <= n; j++) {V[i][j] = cin.nextInt();}}for (int i = 0; i < 2; i++) {for (int f = 1; f <= n; f++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (i == 1)dp[i][f][j][k] = 0;elsedp[i][f][j][k] = INF;if (i == 0 && f == 0)dp[i][f][j][k] = 0;}}}}int Min = INF;for (int i = 1; i < n; i++) {for (int j = 1; j <= n; j++) {for (int k = 1; k <= n; k++) {if (j == k)continue;for (int f = 1; f <= n; f++) {if (f == j)continue;if ((dp[1][i – 1][f][j] & (1 << k)) > 0)continue;if (dp[0][i][j][k] >= dp[0][i – 1][f][j] + V[j][k]) {dp[0][i][j][k] = dp[0][i – 1][f][j] + V[j][k];dp[1][i][j][k] = dp[1][i – 1][f][j] | (1 << k);if (i == n – 1&& Bit_Count(dp[1][i][j][k]) == n – 1) {Min = Math.min(Min, dp[0][i][j][k]);}}}}}}if (Min == INF)cout.println("0");elsecout.println(Min);}cout.flush();}}
带着感恩的心启程，学会爱，爱父母，爱自己，爱朋友，爱他人。
