U43597 积木

题目背景

小 XX 感到很无聊，从柜里翻出了小时候玩的积木。

题目描述

这套积木里共有 \(n\) 块，每块积木都是一个长方体。

小 X 想知道这些积木拼成一个积木塔（不必每一块积木都使用）。

所谓积木塔，就是将积木一个一个摞起来，（除去最底层的积木外）每块积木的底面必须能被它下面的积木的底面完全包含（即对应的长宽都要更短或相等）。

当然，积木可以任意放置，即可以以任意一面作为底面。

现在小 X 想知道，积木塔最多能拼多高。

Solution

状态压缩Dp

\(f(i,j,k)\)表示状态为\(i\)顶为\(j\)且\(j\)的状态(那面朝上)的最大高度,

转移即可.

Code

// luogu-judger-enable-o2

#include <vector>

#include <stdio.h>

#include <string.h>

#include <iostream>

#include <algorithm>

struct Pair {

    int a, b;

    Pair(int _, int __) { a = _, b = __; }

    bool operator <= (const Pair& o) const {

        return (a <= o.a and b <= o.b) or (a <= o.b and b <= o.a);

    }

};

struct cuboid {

    int a, b, c;

    cuboid() { }

    void input() {

        scanf("%d%d%d", &a, &b, &c);

    }

    Pair Choose(int p) {

        return p ? (p < 2 ? Pair(a, b) : Pair(a, c)) : Pair(b, c);

    }

    bool LessOrEqual(cuboid o, int q, int p) {

        Pair A = Choose(p), B = o.Choose(q);

        return A <= B;

    }

};

cuboid A[15];

std:: vector<int> Status[15];

int f[1 << 16][15][3];

int main () {

    int n;

    scanf("%d", &n);

    for (int i = 0; i < n; i += 1)

        A[i].input();

    int Max = (1 << n);

    for (int i = 0; i < Max; i += 1)

        Status[__builtin_popcount(i)].push_back(i);

    for (int i = 0; i < n; i += 1)

        f[1 << i][i][0] = A[i].a, f[1 << i][i][1] = A[i].c, f[1 << i][i][2] = A[i].b;

    int res = 0;

    for (int i = 1; i < n; i += 1) {

      for (int j = 0; j < Status[i].size(); j += 1) {

        int status = Status[i][j];

        for (int k = 0; k < n; k += 1) {

          if (status & (1 << k) == 0) continue;

          for (int w = 0; w < 3; w += 1) {

          	if (not f[status][k][w]) continue;

            res = std:: max(res, f[status][k][w]);

            for (int l = 0; l < n; l += 1) {

                if (status & (1 << l)) continue;

                int sta = status ^ (1 << l);

                if (A[l].LessOrEqual(A[k], w, 0))

                    f[sta][l][0] = std:: max(f[sta][l][0], f[status][k][w] + A[l].a);

                if (A[l].LessOrEqual(A[k], w, 1))

                    f[sta][l][1] = std:: max(f[sta][l][1], f[status][k][w] + A[l].c);

                if (A[l].LessOrEqual(A[k], w, 2))

                    f[sta][l][2] = std:: max(f[sta][l][2], f[status][k][w] + A[l].b);

            }

          }

        }

      }

    }

    for (int i = 0; i < n; i += 1)

        res = std:: max(res, f[Max - 1][i][0]),

        res = std:: max(res, f[Max - 1][i][1]),

        res = std:: max(res, f[Max - 1][i][2]);

    printf("%d\n", res);

    return 0;

}

巴特西

U43597 积木

题目背景

题目描述

Solution

Code

最新文章

热门文章