Problem Description:
Given a sequence a1, a2, ..... an, of positive integers, a strictly increasing subsequence is a subsequence of the given sequence such that each term of the subsequence is strictly less than the next. For example, in the sequence 1, 2, 10, 3, 7 , 4, two strictly increasing sub sequences are 1, 10 and 2, 3, 4
The Input consists of N sets of five integers each. From these sets, a derived sequence is formed by selecting one of the five numbers in each set as part of the sequence.
The objective is to pick the numbers from each set so that the corresponding derived sequence has the strictly increasing subsequence with the largest sum.
Input
The first line of the input has a positive integer N which is the number of sets of the numbers in the input. Each of the next N lines consists of a set of five (not necessarily distinct) comma separated positive integers.
Output
The sum of the elements of the longest strictly increasing subsequence in all possible derived sequences
Constraints
N<=50
Integers in sets<=10000
Example 1
Input:
5
3000,400,1500,4350,2700
2050,3650,650,2750,4300
2000,700,2100,700,1650
300,200,500,600,200
3000,3100,3200,1100,1400
Output:
8850
Explanation:
A possible derived sequence from the input which gives the maximum sum for a strictly increasing subsequence is 1500,2050,2100,500,3200 (one from each row), and the strictly increasing subsequence that gives the maximum sum from this from this is 1500,2050,2100,3200, whose sum is 8850, which is the output
Example 2
Input:
6
800,3000,600,3600,800
1400,5200,1600,6000,2600
3200,3800,3200,1600,2400
800,2800,4800,600,1400
5200,1400,4800,3800,800
5000,4200,4800,1800,2000
Output:
17400
Explanation:
A possible derived sequence that gives a maximum sum for a strictly increasing subsequence is 800, 1600, 2400, 2800, 4800, 5000. All appear in the strictly increasing subsequence, and the sum is 17400, which is the output
Given a sequence a1, a2, ..... an, of positive integers, a strictly increasing subsequence is a subsequence of the given sequence such that each term of the subsequence is strictly less than the next. For example, in the sequence 1, 2, 10, 3, 7 , 4, two strictly increasing sub sequences are 1, 10 and 2, 3, 4
The Input consists of N sets of five integers each. From these sets, a derived sequence is formed by selecting one of the five numbers in each set as part of the sequence.
The objective is to pick the numbers from each set so that the corresponding derived sequence has the strictly increasing subsequence with the largest sum.
Input
The first line of the input has a positive integer N which is the number of sets of the numbers in the input. Each of the next N lines consists of a set of five (not necessarily distinct) comma separated positive integers.
Output
The sum of the elements of the longest strictly increasing subsequence in all possible derived sequences
Constraints
N<=50
Integers in sets<=10000
Example 1
Input:
5
3000,400,1500,4350,2700
2050,3650,650,2750,4300
2000,700,2100,700,1650
300,200,500,600,200
3000,3100,3200,1100,1400
Output:
8850
Explanation:
A possible derived sequence from the input which gives the maximum sum for a strictly increasing subsequence is 1500,2050,2100,500,3200 (one from each row), and the strictly increasing subsequence that gives the maximum sum from this from this is 1500,2050,2100,3200, whose sum is 8850, which is the output
Example 2
Input:
6
800,3000,600,3600,800
1400,5200,1600,6000,2600
3200,3800,3200,1600,2400
800,2800,4800,600,1400
5200,1400,4800,3800,800
5000,4200,4800,1800,2000
Output:
17400
Explanation:
A possible derived sequence that gives a maximum sum for a strictly increasing subsequence is 800, 1600, 2400, 2800, 4800, 5000. All appear in the strictly increasing subsequence, and the sum is 17400, which is the output
No comments:
Post a Comment