江苏建设招投标网,优化资源配置,南阳专业网站建设,去哪网网站设计风格售货员的难题 题目描述输入输出格式输入格式#xff1a;输出格式#xff1a; 输入输出样例输入样例#1#xff1a;输出样例#1#xff1a; 思路AC代码#xff1a; 题目描述
某乡有n个村庄( 1 n 16 )#xff0c;有一个售货员#xff0c;他要到各个村庄去售货输出格式 输入输出样例输入样例#1输出样例#1 思路AC代码 题目描述
某乡有n个村庄( 1 n 16 )有一个售货员他要到各个村庄去售货各村庄之间的路程s(0 s 1000)是已知的且A村到B村与B村到A村的路大多不同。为了提高效率他从商店出发到每个村庄一次然后返回商店所在的村假设商店所在的村庄为1他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。
输入输出格式
输入格式
第一行一个数n表示村庄数 接下来是一个n×n的矩阵表示各村庄之间的路程。
输出格式
最短的路程。
输入输出样例
输入样例#1
3
0 2 1
1 0 2
2 1 0 输出样例#1
3思路
这是一道状压dp所以做这道题之前需要先知道一些关于状态压缩的基本概念。简单来说就是在一般的题目里一个数组即可保存状态。但是有这样的一些题 目它们具有DP问题的特性但是状态中所包含的信息过多如果要用数组来保存状态的话需要四维以上的数组。于是我们就需要通过状态压缩来保存状态而 使用状态压缩来保存状态的DP就叫做状态压缩DP。例如这道售货员难题若有n 个村庄想要表示是否经过每个村庄的状态则需要使用n维数组而采取状态压缩往往利用二进制的整数来简单的表示状态如 0101 0101 0101则表示经过了 1 1 1、 3 3 3号村庄没有经过 2 2 2、 4 4 4号村庄。
我先介绍一下位运算相关的知识
还有几种在状压dp中常见的应用如下 1.判断一个数字x二进制下第i位是不是等于1。
方法if ( ( ( 1 ( i - 1 ) ) x ) 0)
将1左移i-1位相当于制造了一个只有第i位上是1其他位上都是0的二进制数。然后与x做与运算如果结果0说明x第i位上是1反之则是0。
2.将一个数字x二进制下第i位更改成1。
方法x x | ( 1(i-1) )
证明方法与1类似此处不再重复证明。
3.把一个数字二进制下最靠右的第一个1去掉。
方法xx(x-1)
回过头来看这道题n20,使用状态压缩将会很方便dp[i][j]表示从起始点到i号点在j状态下花费的最短路程例如n3,dp[3][3]即表示从起始点到3号点在011也就是经过了1号点和2号点的情况的最短路程。 详细的状态方程可以见代码再填出dp表格后比较不同的点在经过所有点后到起始点的路程便可以得到答案
AC代码
#includeiostream
#includealgorithm
#includecstring
#includecmath
using namespace std;
int map[21][21];
int dp[21][40000];
int main()
{int n;cinn;for(int i1;in;i){for(int j1;jn;j){cinmap[i][j];}}memset(dp,64,sizeof(dp));dp[1][1]0;for(int i0;i(1n);i)//枚举路线{for(int j1;jn;j)//枚举村庄 {if(((1(j-1))i)0)//如果第i号村庄没去过第j号村庄就往下 {for(int q1;qn;q)//枚举村庄 {if(1(q-1)i)//如果第i号村庄去了第q号村庄就往下 {dp[j][1j-1|i]min(dp[j][1j-1|i],dp[q][i]map[q][j]);//dp[j][1j-1|i]为经过i号村庄去j号村庄//dp[q][i]map[q][j]为经过i号村庄去q号村庄再从q号村庄去j号村庄//类似于Floyd}}}}}int ans9999999;for(int i2;in;i){ansmin(ans,dp[i][(1n)-1]map[i][1]);//判断从1号村庄去哪一号村庄可以更快的跑完}coutansendl;return 0;
}
