状压 DP, 对于这种范围给到 20 的, 1<<20 并不大, dp[i][j] 中 i 代表状态, 表当前二十个二进制位中, 有多少点已经走过, j 代表的是当前状态中最后的点什么, 我们维护这个二维数组, 就能得到答案 dp[(1<<n)-1][n-1], 如何转移呢??? 很简单, 我们知道, 一个状态 i, 由另外一个状态转移过来, 一定是另外一个状态的二进制位的点, 走到了新的二进制位 0 的点, 造成了那个点的状态变成二进制状态位 1, 从而产生了新的状态, 那么其实很简单了, 直接转移就行.
- #include <bits/stdc++.h>
- #define LL long long
- using namespace std;
- int n;
- int maps[30][30];
- const int maxx = (1<<20)+2;
- int d[maxx][20];
- const int INF = 0x3f3f3f3f;
- int main(){
- while(~scanf("%d",&n)){
- for (int i=0;i<n;i++){
- for (int j=0;j<n;j++){
- scanf("%d",&maps[i][j]);
- }
- }
- memset(d,0x3f,sizeof(d));
- d[1][0]=0;
- for(int i=1;i<(1<<n);i++){
- for (int j=0;j<n;j++){
- if((i>>j)&1){
- // 代表走过的点中有第 j 号点, i 的第 j 位置的二进制位不为 0
- for (int k=0;k<n;k++){
- if((i^(1<<j))>>k & 1){
- d[i][j]=min(d[i][j],d[i^(1<<j)][k]+maps[j][k]);
- }
- }
- }
- }
- }
- printf("%d\n",d[(1<<n)-1][n-1]);
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3336396.html