首先看一道裸题

题目描述某乡有nn个村庄(1
      
       
        <1000)s(0<1000)是已知的，且A村到B村与B村到A村的路大多不同。为了提高效率，他从商店出发到每个村庄一次，然后返回商店所在的村，假设商店所在的村庄为1，他不知道选择什么样的路线才能使所走的路程最短。请你帮他选择一条最短的路。输入格式村庄数nn和各村之间的路程(均是整数)。输出格式最短的路程。样例一input30 2 11 0 22 1 0output3样例解释3 {村庄数}0 2 1 {村庄1到各村的路程}1 0 2 {村庄2到各村的路程}2 1 0 {村庄3到各村的路程}限制与约定时间限制：1s1s空间限制：256MB
       
      

这道题呢它数据范围小，所以我们能看出是状压DP

它的思路就是，对于每个村庄，访问过为1，没访问过为0，压成一个二进制数

状态是dp[sit][pos]代表当前这个状态，在什么位置

然后对于每一个状态，对于每一个0往上填1，在已有的1（就是已走过的点里），找一个到当前花费最少的，进行状态更新

 dp[sit][v]=min(dp[sit][v],dp[now][u]+in[u][v]); 

也就是这样

这是这道题的代码

1 #include
     
       2 #include
      
        3 #include
       
         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<
       
      
     

我的这种写法会多开一个数组，导致洛谷上的加强数据过不了，但是跑的会很快

1 #include
     
       2 #include
      
        3 #include
       
         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<
       
      
     

这个是巨佬的写法，这么写少开数组，但是会慢一些，重点是它好写，所以推荐第二种，就是暴力枚举，因为从小到大枚举，肯定前面状态更新后面的状态

看第二题

题目描述有一个送外卖的，他手上有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的直接通路时间不一定相同，也就是说道路都是单向的。输出格式一个正整数表示最少花费的时间样例一input30 1 10 101 0 1 210 1 0 1010 2 10 0output8限制与约定时间限制：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
     
       2 #include
      
        3 #include
       
         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<
       
      
     

看第三题

描述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样例输入12-1 97942724 –1Copy样例输出12724Copy限制所有数据时限为1s来源jszx

这道题依旧是接近裸题，和前几道题唯一的区别就是，它不限制起点，从任意点出发都行，就是在赋初值时候加一些东西，输出时扫一遍就OK了

1 #include
     
       2 #include
      
        3 #include
       
         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<
        
         <
        
       
      
     

总结一下

TSP==暴力

其实

状压==暴力