首先看一道裸题
题目描述 某乡有nn个村庄(1<n≤15)(1<n≤15)，有一个售货员，他要到各个村庄去售货，各村庄之间的路程s(0<s<1000)s(0<s<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。 输入格式 村庄数nn和各村之间的路程(均是整数)。 输出格式 最短的路程。 样例一 input 3 0 2 1 1 0 2 2 1 0 output 3 样例解释 3 {村庄数} 0 2 1 {村庄1到各村的路程} 1 0 2 {村庄2到各村的路程} 2 1 0 {村庄3到各村的路程} 限制与约定 时间限制：1s1s 空间限制：256MB
这道题呢它数据范围小，所以我们能看出是状压DP
它的思路就是，对于每个村庄，访问过为1，没访问过为0，压成一个二进制数
状态是dp[sit][pos]代表当前这个状态，在什么位置
然后对于每一个状态，对于每一个0往上填1，在已有的1（就是已走过的点里），找一个到当前花费最少的，进行状态更新
1 dp[sit][v]=min(dp[sit][v],dp[now][u]+in[u][v]);
也就是这样
这是这道题的代码
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define ma 1<<16 5 using namespace std;typedef long long ll; 6 int n,dp[ma][18],in[20][20],situ[17][1<<17],pp[17]; 7 void sou(int id,int num,int sit) 8 { 9 if(id>n){ 10 situ[num][++pp[num]]=sit; 11 if(num==1) 12 { 13 for(int i=1;i<=n;i++) 14 if(sit&(1<<i-1)){dp[sit][i]=in[1][i];break;} 15 } 16 return; 17 } 18 sou(id+1,num+1,sit+(1<<id-1)); 19 sou(id+1,num,sit); 20 } 21 int main() 22 { 23 scanf("%d",&n); 24 for(int i=1;i<=n;i++) 25 for(int j=1;j<=n;j++) 26 scanf("%d",&in[i][j]); 27 memset(dp,0x3f,sizeof(dp)); 28 sou(1,0,0); 29 for(int nn=1;nn<=n;nn++)//有几个1 30 { 31 for(int i=1;i<=pp[nn];i++)//情况编号 32 { 33 int now=situ[nn][i]; 34 for(int v=1;v<=n;v++)//枚举0 35 { 36 if(now&(1<<v-1))continue;//这一位可以填 37 int sit=now+(1<<(v-1)); 38 for(int u=1;u<=n;u++)//枚举1 39 dp[sit][v]=min(dp[sit][v],dp[now][u]+in[u][v]); 40 } 41 } 42 } 43 printf("%d ",dp[(1<<(n))-1][1]); 44 return 0; 45 }
我的这种写法会多开一个数组，导致洛谷上的加强数据过不了，但是跑的会很快
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define rg register 5 using namespace std;typedef long long ll; 6 int n,dp[1<<20][20],in[21][21]; 7 int main() 8 { 9 scanf("%d",&n); 10 for(rg int i=1;i<=n;i++) 11 for(rg int j=1;j<=n;j++) 12 scanf("%d",&in[i][j]); 13 memset(dp,0x3f,sizeof(dp));dp[1][1]=0; 14 for(rg int i=1;i<=n;i++)dp[1<<i-1][i]=in[1][i]; 15 for(rg int sit=0;sit<(1<<n);sit++) 16 { 17 for(rg int v=1;v<=n;v++)//枚举0 18 { 19 if(sit&(1<<v-1))continue;//这一位可以填 20 for(rg int u=1;u<=n;u++)//枚举1 21 if(sit&(1<<u-1)) 22 dp[sit+(1<<(v-1))][v]=min(dp[sit+(1<<(v-1))][v],dp[sit][u]+in[u][v]); 23 } 24 } 25 printf("%d ",dp[(1<<n)-1][1]); 26 return 0; 27 }
这个是巨佬的写法，这么写少开数组，但是会慢一些，重点是它好写，所以推荐第二种，就是暴力枚举，因为从小到大枚举，肯定前面状态更新后面的状态
看第二题
题目描述 有一个送外卖的，他手上有nn份订单，他要把nn份东西，分别送达nn个不同的客户的手上。nn个不同的客户分别在1……n1……n个编号的城市中。送外卖的从0号城市出发，然后nn个城市都要走一次（一个城市可以走多次），最后还要回到0点（他的单位），请问最短时间是多少。现在已知任意两个城市的直接通路的时间。 输入格式 第一行一个正整数n（1≤n≤15）n（1≤n≤15） 接下来是一个（n+1）∗(n+1)（n+1）∗(n+1)的矩阵，矩阵中的数均为不超过10000的正整数。矩阵的ii行jj列表示第i−1i−1号城市和j−1j−1号城市之间直接通路的时间。当然城市aa到城市bb的直接通路时间和城市bb到城市aa的直接通路时间不一定相同，也就是说道路都是单向的。 输出格式 一个正整数表示最少花费的时间 样例一 input 3 0 1 10 10 1 0 1 2 10 1 0 10 10 2 10 0 output 8 限制与约定 时间限制：1s1s 空间限制：256MB
这道题和上一道题几乎一模一样，只不过要多一个最短路的处理，本来想跑spfa，但是数据范围很小，直接Floyd就OK
1 for(rg int i=1;i<=n+1;i++) 2 for(rg int j=1;j<=n+1;j++) 3 scanf("%d",&dis[i][j]); 4 for(int k=1;k<=n+1;k++) 5 for(int i=1;i<=n+1;i++) 6 for(int j=1;j<=n+1;j++) 7 if(dis[i][j]>dis[i][k]+dis[k][j]) 8 dis[i][j]=dis[i][k]+dis[k][j];
就是这样枚举中间点就OK
代码在这里
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 #define rg register 5 using namespace std;typedef long long ll; 6 int n,dp[1<<20][20],dis[20][20]; 7 int main() 8 { 9 scanf("%d",&n); 10 memset(dis,0x3f,sizeof(dis)); 11 for(rg int i=1;i<=n+1;i++) 12 for(rg int j=1;j<=n+1;j++) 13 scanf("%d",&dis[i][j]); 14 for(int k=1;k<=n+1;k++) 15 for(int i=1;i<=n+1;i++) 16 for(int j=1;j<=n+1;j++) 17 if(dis[i][j]>dis[i][k]+dis[k][j]) 18 dis[i][j]=dis[i][k]+dis[k][j]; 19 memset(dp,0x3f,sizeof(dp));dp[1][1]=0; 20 for(rg int i=1;i<=n+1;i++)dp[1<<i-1][i]=dis[1][i]; 21 for(rg int sit=0;sit<(1<<n+1);sit++) 22 { 23 for(rg int v=1;v<=n+1;v++)//枚举0 24 { 25 if(sit&(1<<v-1))continue;//这一位可以填 26 for(rg int u=1;u<=n+1;u++)//枚举1 27 if(sit&(1<<u-1)) 28 dp[sit+(1<<(v-1))][v]=min(dp[sit+(1<<(v-1))][v],dp[sit][u]+dis[u][v]); 29 } 30 } 31 printf("%d ",dp[(1<<n+1)-1][1]); 32 return 0; 33 }
看第三题
描述 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 9794 2724 –1 Copy 样例输出1 2724 Copy 限制 所有数据时限为1s 来源 jszx
这道题依旧是接近裸题，和前几道题唯一的区别就是，它不限制起点，从任意点出发都行，就是在赋初值时候加一些东西，输出时扫一遍就OK了
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 4 using namespace std; 5 int vv[17][17],dp[1<<18][17],n; 6 int main() 7 { 8 scanf("%d",&n); 9 for(int i=1;i<=n;i++) 10 for(int j=1;j<=n;j++) 11 scanf("%d",&vv[i][j]); 12 memset(dp,0x3f,sizeof(dp)); 13 for(int i=1;i<=n;i++) 14 for(int j=1;j<=n;j++)if(i!=j) 15 dp[(1<<i-1)+(1<<j-1)][j]=vv[i][j]; 16 for(int sit=0;sit<=(1<<n)-1;sit++) 17 for(int to=1;to<=n;to++) 18 if(!(sit&(1<<(to-1)))) 19 for(int u=1;u<=n;u++) 20 if(sit&(1<<(u-1))) 21 dp[sit+(1<<(to-1))][to]=min(dp[sit+(1<<(to-1))][to],dp[sit][u]+vv[u][to]); 22 int ans=0x7f7f7f7f; 23 for(int i=1;i<=n;i++) 24 ans=min(ans,dp[(1<<n)-1][i]); 25 printf("%d ",ans); 26 return 0; 27 }
总结一下
TSP==暴力
其实
状压==暴力