Question Name:TOWER OF HANOI

#include <bits/stdc++.h>
#define lli long long
using namespace std;
lli dp[202];
int main()
{
  int t,n;
   lli x,y;
   cin >> t;
   assert(t<=10);
   while ( t-- ) {
      cin >> n;
     assert(n<=200);
       vector < pair<lli,lli> > v;
       for ( int i = 0; i < n; i++ ) {
           cin >> x >> y;
           assert(x<=1000000000);
           assert(y<=1000000000);
           v.push_back(make_pair(x,y));
       }
       sort(v.begin(),v.end());
       dp[0] = v[0].second;
       lli ans = v[0].second;
       for ( int i = 1; i < n; i++ ) {
           dp[i] = v[i].second;
           for ( int j = 0; j < i; j++ ) {
               if ( v[i].second > v[j].second && v[i].first > v[j].first ) dp[i] = max(dp[i], dp[j]+v[i].second);
         }
  ans = max(ans, dp[i]);
       }
       cout << ans << endl;
   }
   return 0;
}
  • Problem Description
    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 ith 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
  • Test Case 1
    Input (stdin)2
    3
    4 3
    1 4
    3 2
    5
    5 6
    4 3
    1 2
    7 5
    3 4
    Expected Output5
    12
  • Test Case 2
    Input (stdin)4
    3
    2 3
    1 5
    6 4
    5
    1 2
    3 1
    4 5
    6 1
    2 6
    2
    6 1
    4 3
    4
    2 6
    1 4
    4 5
    2 2
    Expected Output7
    8
    3
    10

Leave a Reply

Your email address will not be published. Required fields are marked *

Ads Blocker Image Powered by Code Help Pro

Ads Blocker Detected!!!

We have detected that you are using extensions to block ads. Please support us by disabling these ads blocker.

Powered By
CHP Adblock Detector Plugin | Codehelppro