TopCoder SRM 560 - 1000: BoundedOptimization

Problem Statement

定义"项"为两个不同变量相乘。

求一个由多个不同"项"相加，含有n个不同变量的式子的最大值。

另外限制了每一个变量的最大最小值Upperbound[i]和Lowerbound[i]和所有变量之和的最大值Max。

n<=13

You are given an arithmetic expression. The expression is a sum of one or more terms. Each term is a product of exactly two variables. In each term, the two variables are distinct. No two terms contain the same pair of variables.

Additionally, the following constraints are given:

For each i, the i-th variable (0-based index) must have a value between lowerBound[i] and upperBound[i], inclusive. The bounds are integers, but the value of the variable can be any real number in the given range.
The sum of all variables must not exceed maxSum.

You are given a String[] expr, the int[]s lowerBound and upperBound, and the int maxSum. Concatenate the elements of expr to obtain the considered expression. For each i, the i-th variable will be denoted by the i-th lowercase letter of the English alphabet. (Both indices are 0-based, so variable 0 is 'a', variable 1 is 'b', and so on.)

Return the maximum value of the expression, given that all the above constraints have to be satisfied. Note that the constraints guarantee that it is possible to satisfy all the given constraints.

Definition

Class BoundedOptimization
Method maxValue
Parameters vector<string> , vector<int> , vector<int> , int
Returns double
Method signature double maxValue(vector<string> expr, vector<int> lowerBound, vector<int> upperBound, int maxSum)

(be sure your method is public)

Limits

Time limit (s) 2.000
Memory limit (MB) 64

Notes

Your return value must have a relative or an absolute error of less than 1e-9.

Constraints

expr will contain between 1 and 50 elements, inclusive.
Each element of expr will contain between 1 and 50 characters, inclusive.
Each character in each element of expr will be '+' or one of the first n lowercase letters of the English alphabet, where n is the number of elements in lowerBound.
The concatenation of the elements of expr will consist of pairs of letters separated by '+' characters.
No unordered pair of consecutive letters will appear twice in the concatenation of the elements of expr.
No two consecutive letters in the concatenation of the elements of expr will be equal.
lowerBound will contain between 2 and 13 elements, inclusive.
Each element of lowerBound will be between 0 and 100, inclusive.
upperBound will contain n elements, where n is the number of elements in lowerBound.
For each i between 0 and n - 1, the i-th element of upperBound will be between lowerBound[i] and 100, inclusive.
maxSum will be between the sum of the elements of lowerBound and 1,300, inclusive.

Test cases

input
- expr { "ba+cb" }
- lowerBound { 0, 0, 1 }
- upperBound { 1, 2, 1 }
- maxSum 3
output
Returns 2.25

note

The maximum value is obtained by setting a = 0.5, b = 1.5, c = 1.
input
- expr { "ab" }
- lowerBound { 0, 0, 10 }
- upperBound { 20, 20, 20 }
- maxSum 12
output
Returns 1.0

note

We have to set a proper value for c even though it is not present in the expression described by expr.
input
- expr { "ca+fc+fa+d", "b+da+", "dc+c", "b", "+ed+eb+ea" }
- lowerBound { 10, 11, 12, 13, 14, 15 }
- upperBound { 15, 16, 17, 18, 19, 20 }
- maxSum 85
output
Returns 2029.25
input
- expr { "db+ea+ik+kh+je+", "fj+lk+i", "d+jb+h", "a+gk+mb+ml+lc+mh+cf+fd+", "gc+ka+gf+bh+mj+eg+bf+hf+l", "b+al+ja+da+i", "f+g", "h+ia+le+ce+gi+d", "h+mc+fe+dm+im+kb+bc+", "ib+ma+eb+mf+jk+kc+mg+mk+", "gb+dl+ek+hj+dg+hi", "+ch+ga+ca+fl+ij+fa+jl+dc+dj+fk", "+li+jg" }
- lowerBound { 57, 29, 50, 21, 49, 29, 88, 33, 84, 76, 95, 55, 11 }
- upperBound { 58, 80, 68, 73, 52, 84, 100, 79, 93, 98, 95, 69, 97 }
- maxSum 845
output
Returns 294978.3333333333

back to the menu