2023.3.27

整理了一点状压。

拜托，但是我的状压真的学的和个什么东西一样啊。

AcWing 91. 最短Hamilton路径

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 const int N = 21;
 4 int n;
 5 int a[N][N], f[1 << N][N];
 6 int main()
 7 {
 8     scanf("%d", &n);
 9     for(int i = 0; i < n; i ++ )
10         for(int j = 0; j < n; j ++ )
11         {
12             scanf("%d", &a[i][j]);
13             a[j][i] = a[i][j];
14         }
15     memset(f, 0x3f, sizeof f);
16     f[1][0] = 0;
17     for(int i = 2; i < (1 << n); i ++ )
18     {
19         for(int cur = 1; cur < n; cur ++ )
20         {
21             if(! (i & (1 << cur))) continue;
22             for(int pre = 0; pre < n; pre ++ )
23             {
24                 if(! (i & (1 << pre)) || pre == cur) continue;
25                 f[i][cur] = min(f[i][cur], f[i - (1 << cur)][pre] + a[pre][cur]);
26             }
27         }
28     }
29     printf("%d", f[(1 << n) - 1][n - 1]);
30 }

AcWing 291. 蒙德里安的梦想