UVA 103 Stacking Boxes (dp + DAG上的最长路径 + 记忆化搜索)(二)

#include 
#include 
#include 
using namespace std;

int n, m, i, j, Max, dp[35], way[35], save[35];
struct Box {
	int d[15];
} b[35];

int judge(int small, int big) {
	for (int i = 0; i < m; i ++)
		if (b[small].d[i] >= b[big].d[i])
			return 0;
	return 1;
}

void dfs(int now, int num) {
	for (int i = 1; i <= n; i ++) {
		if (i != now && judge(now, i) && dp[i] < num + 1) {//dp[i] < num + 1 是记忆化搜索的关键。
			dp[i] = num + 1;
			save[num] = i;
			dfs(i, num + 1);
		}
	}
	if (Max < num) {
		Max = num;
		for (int j = 0; j < num; j ++)
			way[j] = save[j];
	}
}

int main() {
	while (~scanf("%d%d", &n, &m)) {
		Max = 0;
		memset(dp, 0, sizeof(dp));
		for (i = 1; i <= n; i ++) {
			for (j = 0; j < m; j ++) {
				scanf("%d", &b[i].d[j]);
			}
			sort(b[i].d, b[i].d + m);
		}
		dfs(0, 0);
		printf("%d\n", Max);
		for (i = 0; i < Max - 1; i ++)
			printf("%d ", way[i]);
		printf("%d\n", way[Max - 1]);
	}
	return 0;
}