我上周收到了这个任务，但找不到一个好的算法来解决这个问题。因此，描述如下：
您可以通过不将较大的立方体放入较小的立方体以及不将较硬的立方体放入较轻的立方体中来构建稳定的塔。编写一个程序，为您提供尽可能高的塔，其中有 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
我希望你能帮我解决这个问题。感谢所有帮助
i got this task last week but can't find a good algorithm to solve the problem. So here is the description:
You can build a stable tower with building cubes by not putting bigger cubes to smaller ones and if you don't put harder cubes into lighter ones. Make a programme which gives you the highest possible tower with n number of cubes.
Input:
In the first row of in.txt there is the number of cubes n (1 =< n =<1000). the following n line consisting two positive integer, a cube's sidelength and weight (both of them are not higher than 2000) there are no similar cubes which sidelength and wieght is the same
Output:
you have to write the highest possible stable tower's m number into out.txt. into the second row you have to write in the ordinal number m of the tower from bottom to top. by the height of the tower we mean the amount of all of the cubes's sidelength (not the number of cubes). if there are more than one solution, you can give whatever you want
example for input and output:
input:
5
10 3
20 5
15 6
15 1
10 2
and the output:
3
2 1 5
here are limits on the program. Time limit: 0.2 sec. Memory limit: 16 Mb
I hope you can help me to solve this. thx for all help
发布评论
评论（1）
关系“块A可以放置在块B之上”定义了一个块上的部分顺序。您可以使用卡恩算法（又名“拓扑排序”）将其转换为总计顺序，然后您可以按顺序深度遍历以找到最长路径。
The relationship "block A can be placed on top of block B" defines a partial order on the blocks. You can use Kahn's algorithm (aka "topological sort") to turn this into a total order, which you can then traverse in depth order to find the longest path.