3

我上周接到了这个任务,但找不到一个好的算法来解决这个问题。所以这里是描述:

您可以通过不将较大的立方体放在较小的立方体中并且如果您不将较硬的立方体放入较轻的立方体中来用构建立方体来建造一座稳定的塔。编写一个程序,为您提供具有 n 个立方体的最高塔。
输入:
在 in.txt 的第一行有立方体的数量 n (1 =< n =<1000)。下面的 n 行包含两个正整数,一个立方体的边长和重量(它们都不大于 2000),没有类似的立方体边长和重量相同
输出:
您必须将尽可能高的稳定塔的 m 数写入 out.txt。在第二行中,您必须从下到上写下塔的序数 m。塔的高度是指所有立方体的边长的数量(而不是立方体的数量)。如果有多个解决方案,您可以给出任何您想要
的输入和输出示例:
输入:
5
10 3
20 5
15 6
15 1
10 2
和输出:
3
2 1 5
这是程序的限制。时间限制:0.2 秒。内存限制:16 Mb

我希望你能帮我解决这个问题。谢谢大家的帮助

4

1 回答 1

5

“块A可以放在块B之上”的关系定义了块的偏序。您可以使用Kahn 算法(又名“拓扑排序”)将其转换为总顺序,然后您可以按深度顺序遍历它以找到最长的路径

于 2010-11-25T19:28:33.723 回答