#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
No comments:
Post a Comment