UVa 103 - Stacking Boxes

传送门

UVa 103 - Stacking Boxes

题意

给几个N维的盒子,如果A的所有维度都比对应的小就可以装进去,求可以装的最大个数,并从小到大输出。

思路

这题和矩形嵌套一样,只是从二维扩展到了多维。
话是这么说,但是昨天写过一遍的矩阵嵌套今天又忘了。。又去看了一遍
这里增加了输出路径,只要按照嵌套个数相差1的关系进行输出即可。

代码

#include <cstdio>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
const int MAXN = 40;

struct BOX
{
    int dimen[20];
}box[MAXN];

int dimen, n, dp[MAXN];
bool first;

bool isNested(const BOX &a, const BOX &b)
{
    int i;
    for (i = 0; i < dimen; i++)
        if (a.dimen[i] >= b.dimen[i])
            return false;
    return true;
}

int DFS(int i, const vector<int> *mp)
{
    int &ans = dp[i], temp;
    if (ans != -1)
        return ans;
    ans = 1;
    for (int j = 0; j < mp[i].size(); j++)
    {
        temp = DFS(mp[i][j], mp) + 1;
        ans = max(temp, ans);
    }
    return ans;
}

void PrintAns(int i, const vector<int> *mp)
{
    if (first)
    {
        printf("%d", i + 1);
        first = false;
    }
    else
        printf(" %d", i + 1);
    for (int j = 0; j < mp[i].size(); j++)
    {
        if (dp[mp[i][j]] == dp[i] - 1)
        {
            PrintAns(mp[i][j], mp);
            break;
        }
    }
}

int main()
{
    //freopen("input.txt", "r", stdin);
    int i, j, ans, target;
    while (~scanf("%d%d", &n, &dimen))
    {
        first = true;
        ans = -1;
        memset(dp, -1, sizeof(dp));
        vector<int> mp[MAXN];
        for (i = 0; i < n; i++)
        {
            for (j = 0; j < dimen; j++)
                scanf("%d", &box[i].dimen[j]);
            sort(box[i].dimen, box[i].dimen + dimen);
        }
        for (i = 0; i < n - 1; i++)
            for (j = i + 1; j < n; j++)
            {
                if (isNested(box[i], box[j]))
                    mp[i].push_back(j);
                else if (isNested(box[j], box[i]))
                    mp[j].push_back(i);
            }
            for (i = 0; i < n; i++)
            {
                int temp = DFS(i, mp);
                if (temp > ans)
                {
                    ans = temp;
                    target = i;
                }
            }
            printf("%d\n", ans);
            PrintAns(target, mp);
            printf("\n");
    }
    return 0;
}

Powered by Jekyll and Theme by solid