Description

毛大神最近在玩一个传递游戏，即有 \(N\) 个人在做传递物品的游戏，这 N 个人的编号为 \(1，2，3，...，N-1，N\)。

游戏规则是这样的：开始时物品可以在任意一人手上，他可把物品传递给其他人中的任意一位；下一个人可以传递给未接过物品的任意一人。

即物品只能经过同一个人一次，而且每次传递过程都有一个代价；不同的人传给不同的人的代价值之间没有联系；

毛大神想知道当物品经过所有 \(N\) 个人后，整个过程的最小的代价总和是多少。

Format

Input

第一行为 \(N\)，表示共有 \(N\) 个人；

以下为 N × N 的矩阵，第\(i\)行第 j 列的数为 \(A[i][j]\)，表示物品从编号为 i 的人传递到编号为 j 的人所花费的代价，其中 \(A[i][i]=-1\)（因为物品不能自己传给自己）。

Output

输出共一行一个数，为最小的代价总和。

Samples

输入数据 1
2
-1 9794
2724 -1
输出数据 1
2724
Limitation
对于 50% 的数据，\(1 ≤ N ≤ 11\)；

对于 100% 的数据，\(1 ≤ N ≤ 16；1 ≤ A[i][j] ≤ 10000；A[i][i]=-1\)。

浅浅的谈一下

• 第一反应肯定是搜索，然后回溯，时间复杂度乍一看可以，我们算算

• ……其实我也不会算（一个蒟蒻），为什么不行呢，因为有人试过了，\(45\)分

• 怎么办？

• 一看这题目的问法， 就有一种\(dp\)的思路，配合这数据范围，配合这题目，状压\(dp\)应运而生！

• 什么是状压\(dp\)(其实我写过了，就copy过来了)

• “状压DP 又叫集合动态规划。是以结合信息为状态的特殊的动态规划的问题。主要有传统集合动态规划和基于连通性状态压缩的动态规划两种。” ————百度

• 是不是感觉很高大尚？（我也觉得 ）

• 其实很简单（不是我说的）

• 状压dp的样子

• 我们回到题目：我们把每个人看成每一个点，被传递过标记成一，他就变成了这样一个样子，很想二进制枚举是吧
  

• 怎么转移？

• (\(<<\))：左移

  • 在十进制上是乘法
  • 在二进制上是把整体往左挪一位，例如：\(100 << 1 = 1000\)
  • (\(>>\)): 右移，和左移原理一样，把整体往右移一位
  • 对于每个状态，我们枚举这个点有没有选到：如\(100010\)这个状态没有选第三个点

• 这就要用到左移 和 与运算了

• 如果我想要表示一个\(100\)，表示第三个状态已被选怎么办？

• 很容易发现\(100=1<<(3-1)\)

• 于是我们可以总结:\(想要表示第i个点被选=1<<(i-1)\)

• 于是我们就可以用\(i\&1<<(j-1)\)(\(i\)表示当前状态，\(j\)表示当前枚举到的点)来表示\(i\)状态有没有选点\(j\)

• 考虑转移?

• 枚举每个状态，再枚举这个状态选了那些点，再由这些点进行转移

• 什么意思？

• 例如状态\(10001\)，这个状态包含\(1,5\)这\(2\)个点

• 如果点\(2\)可以接到点\(1\)后面

• 那么\(f[11001]=\max(\min)(f[10001]+v,f[11001])\)

• 然后输出\(f[(1<<n)-1]\)全部点被选即可

• 这道题咋写

• 假如枚举到一个状态\(T\),枚举这个状态有多少个存在的点，再由这个点去转移到另外没有被选过的点

• 等等，怎么判断\(T\)中，球传到哪里了？

• 于是，我们就要开二维数组$dp_{iT}到了第i个人，状态为T $

• 于是就有我们的满分代码了（注意\(<<\)的优先级！）

\(Code\)

#include<bits/stdc++.h>
//值得写解题报告! 
using namespace std;
int dp[20][1<<20],n,g[20][20];
//dp[i][T]到了第i个人，状态为T 
int main(){
	cin>>n;
	for(int i=1;i<=n;i++) 
		for(int j=1;j<=n;j++)
			cin>>g[i][j];
	memset(dp,0x3f,sizeof(dp));
	for(int i=1;i<=n;i++)dp[i][1<<(i-1)]=0;//初始 
	for(int t=1;t<1<<n;t++)//枚举状态
		 for(int i=1;i<=n;i++)
		 	if(t&(1<<i-1))//在这里面 
		 		for(int j=1;j<=n;j++)
		 			if(i!=j&&!(t&(1<<j-1)))//不在这里面
					 	dp[j][t|(1<<j-1)]=min(dp[j][t|(1<<j-1)],dp[i][t]+g[i][j]);
	int ans=1e9;
	for(int i=1;i<=n;i++)
		ans=min(ans,dp[i][(1<<n)-1]);
	cout<<ans<<endl;
	return 0;//注意"<<"优先级比"-"小 
}

题外话：普及组的题竟然会考状压，没想到