博客

题意：

给n种立方体，每种立方体有无限个，摆积木，要求是在下面的那个立方体的上面比上面那个立方体的下面大，才可摆放。

解析：

数据量不大，因此枚举出立方体的6种摆放形态，然后按照面积从小到大排序，求解最大子序列和即可。

状态转移方程： dp[ i ]  = max( dp[ i ] , dp[ j ] + r[ i ] . z )

解释，对于第 i 个立法体，用不用，不用即dp[i]，高度保持原最大状态； 用，则高度为使用j个时立方体的最大高度加上第i个立方体的高度。

代码：

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <stack>
#include <vector>
#include <queue>
#include <map>

#define LL long long

using namespace std;
const int maxn = 30 + 10;
const int inf = 0x3f3f3f3f;

struct Rectangular
{
    int x, y, z;
    void f(int a, int b, int c){x = a, y = b, z = c;}
} r[maxn * 6];

int dp[maxn * 6];

bool cmp(Rectangular a, Rectangular b)
{
    return a.x * a.y < b.x * b.y;
}

int main()
{
    #ifdef LOCAL
    freopen("in.txt", "r", stdin);
    #endif // LOCAL
    int n;
    int ca = 1;
    while (scanf("%d", &n) && n)
    {
        memset(dp, 0, sizeof(dp));
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            int x, y, z;
            scanf("%d%d%d", &x, &y, &z);
            r[cnt++].f(x, y, z);
            r[cnt++].f(x, z, y);
            r[cnt++].f(y, x, z);
            r[cnt++].f(y, z, x);
            r[cnt++].f(z, x, y);
            r[cnt++].f(z, y, x);
        }
        sort(r, r + cnt, cmp);
        int ans = 0;
        for (int i = 0; i < cnt; i++)
        {
            dp[i] = r[i].z;
            for (int j = 0; j < i; j++)
            {
                if (r[j].x < r[i].x && r[j].y < r[i].y)
                {
                    dp[i] = max(dp[i], dp[j] + r[i].z);
                }
            }
            if (ans < dp[i])
                ans = dp[i];
        }
        printf("Case %d: maximum height = %d\n", ca++, ans);
    }
    return 0;
}