tower-of-hanoi-17

Bob and Alice like to play the game tower of Hanoi. One day Alice challenges Bob to build the tallest tower from a
set of disks of different height and radius. The tower of Hanoi can be built by stacking disks on top of each other. In order to put disk A on top of disk B, the radius and height of A must be strictly smaller than those of B.  Help Bob to win the challenge.

Input:
First line of input contains number of test cases T.
First line of each test case contains value of  N, the number of disks. The next N lines contains two positive integer number Ri and Hi corresponding to the radius and height of i^th Disk respectively.

Output:
For each test case print the maximum height of the tower possible.  

Constraints:
1 ≤ T ≤ 10
1 ≤ N ≤ 200
1 ≤ Ri, Hi ≤ 10^9

SAMPLE INPUT
2
3
4 3
1 4
3 2
5
5 6
4 3
1 2
7 5
3 4SAMPLE OUTPUT
5
12

Difficulty: EASY
Tags: Dynamic programming
Skill types: Dynamic programming

Starter code:

Solutions:
cases = int(input())
rings = []

for x in range(cases):
	num = int(input())
	rings.append(tuple(tuple(map(int, input().split())) for alpha in range(num)))

height = lambda x: sum(a[1] for a in x)

def hanoi(dims, memo={}):
	if len(dims) == 1:
		return dims

	elif dims in memo:
		return memo[dims]

	else:
		max_height = (dims[-1],)

		for index in range(1, len(dims)):
			till_index = hanoi(dims[:index], memo)
			if till_index[-1][0] < dims[-1][0] and till_index[-1][1] < dims[-1][1]:
				till_index += (dims[-1],)
				if height(till_index) > height(max_height):
					max_height = till_index

		memo[dims] = max_height

		return max_height

for case in rings:
	memo = {}
	output = hanoi(tuple(sorted(case)), memo)
	print((height(max(list(memo.values()), key=height))))



''' HackerEarth - Tower Of Hanoi
	NguyenDatSE '''
	
DISK_H = 1
DISK_R = 0
T = int(input())
Ts = []
for t in range(T):
	N = int(input())
	Ns = []
	for n in range(N):
		Ns.append(list(map(int, input().split())))
	Ts.append(Ns)

class TowerOfHanoi:
	def __init__(self, disks):
		self.disks = disks
		self.ndisks = len(self.disks)
		self.maxh = [0 for n in range(self.ndisks + 1)]

		self.disks.sort()

	# Dynamic Programming to find maximum height obtainable
	def findMaxHeight(self):
		self.maxh[0] = self.disks[0][DISK_H]
		current_max = self.disks[0][DISK_H]

		for i in range(1, self.ndisks):
			self.maxh[i] = self.disks[i][DISK_H]
			for j in range(i):
				if (self.disks[i][DISK_H] > self.disks[j][DISK_H])\
					and self.disks[i][DISK_R] > self.disks[j][DISK_R]:
					self.maxh[i] = max(self.maxh[i], self.maxh[j]+ self.disks[i][DISK_H])
			current_max = max(self.maxh[i], current_max)
		return current_max

for t in range(T):
	solver = TowerOfHanoi(Ts[t])
	print(solver.findMaxHeight())



for _ in range(eval(input())):
	n=eval(input())
	l=[[] for i in range(n)]
	for i in range(n):
		l[i]=list(map(int,input().split()))
	
	l.sort()
	l.reverse()
	m=[]
	for i in l:
		m.append(i[1])
	for i in range(1,n):
		for j in range(i):
			if l[i][0]<l[j][0] and l[i][1]<l[j][1]:
				m[i]=max(m[i],m[j]+l[i][1])
	print(max(m))


'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys
import os
import time

tc=input("")
tc=(int)(tc)

for i in range(tc):
	N=input("")
	N=(int)(N)
	L=[]
	for j in range(N):
		R,H=input("").split(" ")
		L.append(((int)(R),(int)(H)))
	L=sorted(L,key=lambda x:x[0])
	
	dp=[]
	dp.append(L[0][1])
	for j in range(1,N):
		LL=[0]
		for x in range (j-1,-1,-1):
			if L[j][1] > L[x][1] and L[j][0] != L[x][0] :
				LL.append(dp[x])
		val=L[j][1]+max(LL)
		dp.append(val)
	print(max(dp))
	
			
		
		


cases = int(input())
rings = []

for x in range(cases):
	num = int(input())
	rings.append(tuple(tuple(map(int, input().split())) for alpha in range(num)))

height = lambda x: sum(a[1] for a in x)

def hanoi(dims, memo={}):
	if len(dims) == 1:
		return dims

	elif dims in memo:
		return memo[dims]

	else:
		max_height = (dims[-1],)

		for index in range(1, len(dims)):
			till_index = hanoi(dims[:index], memo)
			if till_index[-1][0] < dims[-1][0] and till_index[-1][1] < dims[-1][1]:
				till_index += (dims[-1],)
				if height(till_index) > height(max_height):
					max_height = till_index

		memo[dims] = max_height

		return max_height

for case in rings:
	memo = {}
	output = hanoi(tuple(sorted(case)), memo)
	print((height(max(list(memo.values()), key=height))))



'''
# Read input from stdin and provide input before running code

name = raw_input('What is your name?\n')
print 'Hi, %s.' % name
'''
import sys

testCases = int(sys.stdin.readline())

class Tower:
	def __init__(self, totalHeight, startingHeight):
		self.tHeight = totalHeight
		self.sHeight = startingHeight
		
while testCases > 0:
	rDict = {}
	numDisks = int(sys.stdin.readline())
	rList = []
	
	while numDisks > 0:
		curLine = sys.stdin.readline()
		r = int(curLine.split()[0])
		h = int(curLine.split()[1])
		
		if r not in rDict:
			rDict[r] = []
			rList.append(r)
	
		if h not in rDict[r]:
			rDict[r].append(h)
			
		numDisks = numDisks - 1
		
	
	subTowers = []
	subTowers.append(Tower(0,0))
	maxHeight = 0
	rList.sort()
	
	# just iterate through known r's
	for radius in rList:
		towersToRemove = []
		towersToAdd = []
		# for the disks at that particular radius
		for height in rDict[radius]:
			
			# Find the max tower you could make with Disk(r,h) as the base
			curMaxSubtowerHeight = 0
			for subTower in subTowers:
				# we're iterating by R, so we know R is greater as well
				if (height > subTower.sHeight) and (subTower.tHeight > curMaxSubtowerHeight):
					curMaxSubtowerHeight = subTower.tHeight
			newTower = Tower(height + curMaxSubtowerHeight, height)
			
			# Consider the ramifications of adding this tower to the subtowers list
			# Wait till after we're done considering this RADIUS to add them all
			shouldAddTower = True;
			for tower in subTowers:
				# if newTower is directly inferior to another subtower, break and don't add it 
				if (newTower.sHeight >= tower.sHeight) and (newTower.tHeight <= tower.tHeight):
					shouldAddTower = False
					break
				# if newTower is directly superior to this subtower, note that we should remove it later
				if (tower.sHeight >= newTower.sHeight) and (tower.tHeight <= newTower.tHeight):
					towersToRemove.append(tower)
			
			if shouldAddTower:
				towersToAdd.append(newTower)
					
		for badTower in towersToRemove:
			if badTower in subTowers:
				subTowers.remove(badTower)
				
		for goodTower in towersToAdd:
			reallyReallySureWeShouldAddTower = True
			for otherTower in towersToAdd:
				if (goodTower.sHeight >= otherTower.sHeight) and (goodTower.tHeight < otherTower.tHeight):
					reallyReallySureWeShouldAddTower = False
			if reallyReallySureWeShouldAddTower:
				subTowers.append(goodTower)
				if(goodTower.tHeight > maxHeight):
					maxHeight = goodTower.tHeight
					
	print(maxHeight)
	testCases = testCases - 1


t = int(input())
for i in range(t):
	a = []
	n = int(input())
	for i in range(n):
		arr = list(map(int , input().split()))
		a.append([arr[0] , arr[1]])
	a = sorted(a )
	h = [0 for i in range(n)]
	h[0] = a[0][1]
	for i in range(1 , n):
		h[i] = a[i][1]
		for j in range(i):
			if a[i][0] >  a[j][0] and a[i][1] > a[j][1]:
				h[i] = max ( h[i] , h[j] + a[i][1] )
	print(max(h))