设为首页 加入收藏

TOP

UVA 103 Stacking Boxes (dp + DAG上的最长路径 + 记忆化搜索)(二)
2014-11-23 21:42:20 来源: 作者: 【 】 浏览:10
Tags:UVA 103 Stacking Boxes DAG 最长 路径 记忆 搜索
化搜索。。用一个dp数组来记录套了几个。如果搜索过程中小于的直接不考虑
代码:
#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;
}


首页 上一页 1 2 下一页 尾页 2/2/2
】【打印繁体】【投稿】【收藏】 【推荐】【举报】【评论】 【关闭】 【返回顶部
分享到: 
上一篇 poj 3150 Cellular Automaton 下一篇pat 1055. The World's Riche..

评论

帐  号: 密码: (新用户注册)
验 证 码:
表  情:
内  容:

·一篇说人话的文章, (2025-12-27 07:50:09)
·Python Web框架哪家 (2025-12-27 07:50:06)
·基于Python的数据分 (2025-12-27 07:50:03)
·深入理解 Java 集合 (2025-12-27 07:22:48)
·Java集合框架全面解 (2025-12-27 07:22:45)