CF2041C

_N4F1hC_ · 2026-03-06 09:16:36 · 题解

题目传送门

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];
}