2026 杭电春季联赛 3——1003-3X3安全箱

题目大意

题目描述
有一个大小为 $3 \times 3$ 的矩形安全箱。
共有 $n$ 件物品，第 $i$ 件物品的大小为 $a_i \times b_i$（可以水平放置或旋转 $90^{\circ}$），价值为 $v_i$。
你需要选择若干件物品放入安全箱内，物品必须完全在箱子内部且互相之间不能有重叠部分。
求能够放入安全箱内物品的最大总价值。

输入格式
第一行输入一个整数 $T$（$1 \le T \le 10000$），表示测试数据的组数。
对于每组数据：
第一行输入一个正整数 $n$（$1 \le n \le 10^6$），表示物品的数量。
接下来 $n$ 行，每行输入三个整数 $a_i, b_i, v_i$（$1 \le a_i, b_i \le 3, 1 \le v_i \le 10^8$），分别代表第 $i$ 件物品的长、宽和价值。
保证所有测试组的 $n$ 之和不超过 $10^6$。

输出格式
对于每组数据，输出一行一个整数，表示最大的总价值。

样例输入

2
5
2 3 20
1 3 5
1 2 4
1 1 4
1 3 6
2
1 1 13141314
3 3 6947311

样例输出

28
13141314

样例解释第一组数据：最优策略是放入第 $1$ 件物品（大小 $2 \times 3$，价值 $20$）、第 $3$ 件物品（大小 $1 \times 2$，价值 $4$）以及第 $4$ 件物品（大小 $1 \times 1$，价值 $4$）。第 $1$ 件物品占用 $2 \times 3$ 的空间后，安全箱还会剩余 $1 \times 3$ 的空白区域，恰好可以无重叠地容纳第 $3$ 件和第 $4$ 件物品。总价值为 $20 + 4 + 4 = 28$。
第二组数据：虽然第 $2$ 件物品（大小 $3 \times 3$，价值 $6947311$）能正好填满整个安全箱，但只放入第 $1$ 件物品（大小 $1 \times 1$，价值 $13141314$）可以获得更高的总价值。因此最优选择是仅放置第 $1$ 件物品，最大总价值为 $13141314$。

思路讲解

不难发现，一共只有 21 种有效状态。

开个玩笑，这个是提前用 dfs 跑出来的，直接打表，跳过这个预处理。

那你都预处理出来所有的这个情况了，做起来就很简单了。

AC代码

AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=13515

源代码

// teamname: Gospel_rock
/**
 * Problem: 3X3安全箱
 * Contest: 
 * Judge: HDOJ
 * URL: https://acm.hdu.edu.cn/contest/problem?cid=1199&pid=1003
 * Created: 2026-04-03 19:40:16
 * Author: Gospel_rock
 * My blog: https://znzryb.com/
 * 
 * Powered by AutoCp https://github.com/Pushpavel/AutoCp
 */

#include <bits/stdc++.h>
#define all(vec) vec.begin(),vec.end()
#define lson(o) (o<<1)
#define rson(o) (o<<1|1)
#define SZ(a) ((long long) a.size())
#define debug(var) cerr << #var <<" = ["<<var<<"]"<<"\n";
#define debug1d(a)                          \
cerr << #a << " = [";                     \
for (int i = 0; i < (int)(a).size(); i++) \
cerr << (i ? ", " : "") << a[i];        \
cerr << "]\n";
#define debug2d(a)                               \
cerr << #a << " = [\n";                        \
for (int i = 0; i < (int)(a).size(); i++)      \
{                                              \
cerr << "  [";                               \
for (int j = 0; j < (int)(a[i]).size(); j++) \
cerr << (j ? ", " : "") << a[i][j];        \
cerr << "]\n";                               \
}                                              \
cerr << "]\n";
#define cend cerr<<"\n-----------\n"
#define fsp(x) fixed<<setprecision(x)

using namespace std;

using ll = long long;
using ull = unsigned long long;
using DB = double;
using i128 = __int128;
using CD = complex<double>;

static constexpr ll MAXN = (ll) 1e6 + 10, INF = (1ll << 61) - 1;
static constexpr ll mod = 998244353; // (ll)1e9+7;
static constexpr double eps = 1e-8;
const double PI = acos(-1.0);

ll lT, testcase;

/*
 *
 */

struct Solve {
    ll N;
    // inline 在 C++17 之后扩展到了变量，
    // 成为了解决“如何在头文件/类定义中
    // 直接定义并初始化静态/全局变量
    // 而不会引发多重定义错误”的终极方案。

    static inline vector<vector<ll> > Idx;
    static inline bool is_init;

    static inline vector<vector<char> > vis_dfs;
    static inline set<vector<ll> > st_dfs = {
        {0, 0, 0, 0, 0, 0, 1}, {0, 0, 0, 1, 0, 1, 0}, {0, 0, 0, 3, 0, 0, 0}, {0, 0, 1, 1, 1, 0, 0},
        {0, 0, 3, 1, 0, 0, 0}, {0, 1, 1, 0, 0, 1, 0}, {0, 1, 1, 2, 0, 0, 0}, {0, 1, 2, 0, 1, 0, 0},
        {0, 1, 4, 0, 0, 0, 0}, {0, 2, 0, 1, 1, 0, 0}, {0, 2, 2, 1, 0, 0, 0}, {0, 3, 0, 0, 0, 1, 0},
        {0, 3, 0, 2, 0, 0, 0}, {0, 3, 1, 0, 1, 0, 0}, {0, 3, 3, 0, 0, 0, 0}, {0, 4, 1, 1, 0, 0, 0},
        {0, 5, 0, 0, 1, 0, 0}, {0, 5, 2, 0, 0, 0, 0}, {0, 6, 0, 1, 0, 0, 0}, {0, 7, 1, 0, 0, 0, 0},
        {0, 9, 0, 0, 0, 0, 0}
    };
    // static inline vector<ll> cnt_dfs = vector<ll>(7);
    //
    // static bool check_dfs(ll x, ll i, ll y, ll j) {
    //     for (int fx = x; fx <= x + i - 1; ++fx) {
    //         for (int fy = y; fy <= y + j - 1; ++fy) {
    //             if (fy > 3 || fx > 3) {
    //                 return false;
    //             }
    //             if (vis_dfs[fx][fy]) {
    //                 return false;
    //             }
    //         }
    //     }
    //     return true;
    // }
    //
    // static void flag_dfs_vis(ll x, ll i, ll y, ll j, char val) {
    //     for (int fx = x; fx <= x + i - 1; ++fx) {
    //         for (int fy = y; fy <= y + j - 1; ++fy) {
    //             vis_dfs[fx][fy] = val;
    //         }
    //     }
    // }
    //
    // static void dfs() {
    //     bool flag = false;
    //     for (int x = 1; x <= 3; ++x) {
    //         for (int y = 1; y <= 3; ++y) {
    //             for (int i = 1; i <= 3; ++i) {
    //                 for (int j = 1; j <= 3; ++j) {
    //                     if (check_dfs(x, i, y, j)) {
    //                         flag_dfs_vis(x, i, y, j, 1);
    //                         flag = true;
    //                         cnt_dfs[Idx[min(i, j)][max(i, j)]]++;
    //                         dfs();
    //                         cnt_dfs[Idx[min(i, j)][max(i, j)]]--;
    //                         flag_dfs_vis(x, i, y, j, 0);
    //                     }
    //                 }
    //             }
    //         }
    //     }
    //     if (!flag) {
    //         st_dfs.insert(cnt_dfs);
    //     }
    // }
    void init() {
        is_init = true;
        Idx.resize(4, vector<ll>(4));
        vis_dfs.resize(4, vector<char>(4));
        ll idx = 0;
        for (int i = 1; i <= 3; ++i) {
            for (int j = i; j <= 3; ++j) {
                ++idx;
                Idx[i][j] = idx;
            }
        }
        // dfs();
        // #ifdef LOCAL
        //         debug(SZ(st_dfs));
        //         cerr << "{";
        //         for (auto it: st_dfs) {
        //             cerr << "{";
        //             for (int i = 0; i < SZ(it); ++i) {
        //                 if (i == SZ(it) - 1) {
        //                     cerr << it[i];
        //                 } else {
        //                     cerr << it[i] << ",";
        //                 }
        //             }
        //             cerr << "}";
        //             cerr<<",";
        //         }
        //         cerr << "}";
        // #endif
    }

    vector<vector<ll> > mat;
    vector<vector<ll> > mat_sum;

    Solve() {
        cin >> N;
        if (!is_init) {
            init();
        }
        mat.resize(7);
        mat_sum.resize(7);
        // for (int i=1;i<7;++i) {
        //     mat[i].reserve();
        // }
        for (int i = 0; i < N; ++i) {
            ll a, b, v;
            cin >> a >> b >> v;
            if (a > b) {
                swap(a, b);
            }
            ll type = Idx[min(a, b)][max(a, b)];
            mat[type].push_back(v);
        }
        for (int i = 1; i < 7; ++i) {
            sort(all(mat[i]), greater<>());
            mat_sum[i].resize(max(1ll,SZ(mat[i])));
            partial_sum(all(mat[i]), mat_sum[i].begin());
            mat_sum[i].resize(max(10ll,SZ(mat[i])), mat_sum[i].back());
        }
        ll ans = 0;
        for (auto vec: st_dfs) {
            ll lans = 0;
            for (int i = 1; i < 7; ++i) {
                if (vec[i] > 0) {
                    lans += mat_sum[i][vec[i] - 1];
                }
                // #ifdef LOCAL
                //                 debug1d(mat_sum[i]);
                // #endif
            }

            ans = max(ans, lans);
        }
        cout << ans << "\n";
    }
};

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
#ifdef LOCAL
    cout.setf(ios::unitbuf); // 无缓冲流，方便我们调试
#endif

    cin >> lT;
    for (testcase = 1; testcase <= lT; ++testcase)
        Solve solve;
    return 0;
}

/*
AC
https://acm.hdu.edu.cn/contest/view-code?cid=1199&rid=13515

*/

心路历程（WA，TLE，MLE……）

常见 dfs 错误及原因