uva103 - Stacking Boxes(DAG)

uva103 - Stacking Boxes(DAG)

題目：uva103 - Stacking Boxes(DAG)

題目大意：給出N個boxes， 並且給出這些箱子的維度，要求找一個最長的序列，能夠使得下面的箱子一定能夠有個維度序列大於上面的那個箱子的維度序列。例如：A箱子（2 3 4），B箱子（3 4 5），因為有個序列2 3 4 ， 3 4 5使得B每個維度的值都大於A，所以A可以在B上面 。

解題思路：DAG。將這些箱子哪個能在哪個上面處理出有向圖出來，這裡判斷是否可以在上面的情況，只要將這兩個箱子的維度都從小到大排下序，然後比較一下是否對應的位置的值要不都比另一個小就可以了。

例如 ：

31 4 18 8 27 17

44 32 13 19 41 19

排序

4 8 17 18 27 31

13 19 19 32 41 44

發現上面的數字比下面的對應位置的數字小，就可以。

代碼：

#include 
#include 
#include 
using namespace std;

const int N = 35;
const int M = 15;

int n, m;
int box[N][M];
int G[N][N];
int f[N][N];
int path[N][N];

bool judge (int a, int b) {

	for (int i = 0; i < m; i++)
		if (box[a][i] >= box[b][i])
			return false;
	return true;
}

void handle () {

	memset (G, 0, sizeof (G));
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++) {

			if (i == j)
				continue;
			if (judge(i, j))
				G[i][j] = 1;
		}
}

void init () {

	for (int i = 0; i <= n; i++)
		for (int j = 0; j <= n; j++)
			f[i][j] = -1;
}

int dp (int x, int y) {

	int& ans  = f[x][y];
	int temp;
	if (ans != -1)
		return ans;
	for (int i = 0; i < n; i++)
		if (G[y][i]) {
			temp = dp(y, i) + 1;
			if (temp > ans) {
				ans = temp;
				path[x][y] = i;
			}
		}
	if (ans == -1) {
		ans = 2;
		path[x][y] = -1;
	}
	return ans;
}

void printf_ans(int x, int y) {

	if (path[x][y] == -1)
		return;
	printf (" %d", path[x][y] + 1);
	printf_ans(y, path[x][y]);
}

int main () {

	while (scanf ("%d%d", &n, &m) != EOF) {

		for (int i = 0; i < n; i++)
			for (int j = 0; j < m; j++)
				scanf ("%d", &box[i][j]);

		for (int i = 0; i < n; i++)
			sort (box[i], box[i] + m);
		
		handle ();
		init();

		int ans = 1;
		int temp;
		int x, y;
		for (int i = 0; i < n; i++)
			for (int j = 0; j < n; j++)
				if (G[i][j]) {
					temp = dp(i, j);
					if (temp > ans) {
						ans = temp;
						x = i;
						y = j;
					}
				}
		printf ("%d\n", ans);
		if (ans != 1) { 

			printf("%d %d", x + 1, y + 1);
			printf_ans(x, y);
		} else
			printf ("1");
		printf ("\n");
	}
	return 0;
}