3

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

Poko
  • 31
  • 1
  • 3

1 Answers1

5

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.

Gareth Rees
  • 64,967
  • 9
  • 133
  • 163
  • All I can think about when I hear that algorithms name is William Shatner uttering "KHANNN!!!!" – GWW Nov 25 '10 at 19:39
  • +1. Of course, once you recognize that it's just finding the longest path in a partial order (or DAG), there are many algorithms for doing so. – ShreevatsaR Nov 25 '10 at 20:10
  • i found LIS for a way to solve the problem. But don't know how to use it correctly. would someone tell me how can the problem be solved with it? – Poko Nov 25 '10 at 20:35
  • I don't see an easy way to transform your problem into the [longest increasing subsequence](http://en.wikipedia.org/wiki/Longest_increasing_subsequence) problem, so algorithms to solve the latter will not be of much use to you. – Gareth Rees Nov 25 '10 at 20:42
  • 1
    ok so can u please explain me how to use the algorithms u recommended. i read a lot of times u written but can't rly understand it. :( – Poko Nov 25 '10 at 20:56