ACM 103 Stacking Boxes

Greedy problem. For each box, sort each dimension from biggest to smallest. Then, sort all boxes from smallest to biggest. Apply some dynamic programming and viola!

	// acm uva 103 stacking boxes
	// sirpoot
	#include <iostream>
	#include <algorithm>
	using namespace std;
	#define MAX 30
	int dimension;
	int num_box;
	int** box;
	int max_length[MAX];
	int from[MAX];
	int label[MAX];
	using namespace std;
	bool can_nest(int* inner, int* outer)
	{
	for (int i=0;i<dimension;i++)
	{
	if (inner[i] >= outer[i])
	return false;
	}
	return true;
	}
	void recursePrint(int box)
	{
	if (from[box] != -1)
	recursePrint(from[box]);
	cout << label[box] << " ";
	}
	int main()
	{
	while (cin >> num_box >> dimension)
	{
	// input
	box = new int*[num_box];
	for (int i=0;i<num_box;i++)
	{
	box[i] = new int[dimension];
	for (int k=0;k<dimension;k++)
	{
	cin>>box[i][k];
	}
	sort(box[i], box[i]+dimension);
	}
	// done input, init
	for (int i=0;i<MAX;i++)
	for (int j=0;j<MAX;j++)
	{
	max_length[i] = 1;
	from[i] = -1;
	label[i] = i+1;
	}
	// done init, process
	// first, sort boxes from smallest to biggest
	for (int i=0;i<num_box;i++)
	{
	for (int j=i-1;j>=0;j--)
	{
	if (can_nest(box[j+1],box[j]))
	{
	int* temp;
	// swap box
	temp = box[j];
	box[j] = box[j+1];
	box[j+1] = temp;
	// swap label
	int temp2;
	temp2 = label[j];
	label[j] = label[j+1];
	label[j+1] = temp2;
	}
	}
	}
	// do the DP
	for (int i=0;i<num_box;i++)
	{
	// with i as end point
	for (int j=i-1;j>=0;j--)
	{
	if (i==j) continue;
	if (can_nest(box[j],box[i]))
	{
	if (max_length[j] + 1 >= max_length[i])
	{
	max_length[i] = max_length[j] + 1;
	from[i] = j;
	}
	}
	}
	}
	// processing done, analyze results
	int max_max_length = 0;
	int max_box = -1;
	for (int i=0;i<num_box;i++)
	{
	if (max_length[i] > max_max_length)
	{
	max_max_length = max_length[i];
	max_box = i;
	}
	}
	// analysis done, output
	cout << max_max_length << "\n";
	recursePrint(max_box);
	cout <<"\n";
	}
	return 0;
	}

view raw gistfile1.txt hosted with ❤ by GitHub