题目传送门
Duel 时跳到这题还是比对手慢了四分钟，我已急哭
朴素 dp 很难去重，又 \(n \le 12\)，考虑状压。
设 \(dp_{i,j,k}\) 表示枚举到第 \(i\) 面，第 \(l\) 行是否已经填了格子（若 \(j\) 二进制下从右往左数第 \(l\) 位为 \(1\) 表示填过，否则表示没填过），第 \(m\) 列是否已经填了格子（若 \(k\) 二进制下从右往左数第 \(m\) 位为 \(1\) 表示填过，否则表示没填过），那么可以得到转移方程
int j2 = j - (1 << (l - 1)),k2 = k - (1 << (m - 1));
dp[i][j][k] = min(dp[i][j][k],dp[i - 1][j2][k2] + a[i][l][m]);
但是因为前 \(i\) 面会填 \(i\) 个格子，需要注意 \(j\) 和 \(k\) 二进制位都恰好是 \(i\) 个 \(1\)，并且 \(j\) 二进制下从右往左数第 \(l\) 位与 \(k\) 二进制下从右往左数第 \(m\) 位也都是 \(1\)。
那么复杂度理应是 \(\mathcal{O}(n^3 \times 2^{2n})\)，但是有了那么多剪枝后一定跑不满，可以在八九百毫秒的时间内跑过这道题。
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
#define lowbit(x) x&(-x)
using namespace std;
int n,a[55][55][55],dp[13][4098][4098],ans;
signed main()
{cin >> n;memset(dp,0x3f,sizeof(dp));dp[0][0][0] = 0;for(int i = 1;i <= n;i ++){for(int j = 1;j <= n;j ++)for(int k = 1;k <= n;k ++)cin >> a[i][j][k];}for(int i = 1;i <= n;i ++){for(int j = 0;j < (1 << n);j ++){if(__builtin_popcount(j) != i)continue ;//可以算某个数二进制位中1的个数for(int k = 0;k < (1 << n);k ++){if(__builtin_popcount(k) != i)continue ;for(int l = 1;l <= n;l ++){if((j >> (l - 1)) % 2 == 0)continue ;for(int m = 1;m <= n;m ++){if((k >> (m - 1)) % 2 == 0)continue ;int j2 = j - (1 << (l - 1)),k2 = k - (1 << (m - 1));dp[i][j][k] = min(dp[i][j][k],dp[i - 1][j2][k2] + a[i][l][m]);//状态转移}}}}}cout << dp[n][(1 << n) - 1][(1 << n) - 1];
}