TopCoder problem "ElectiveSystem" used in TCHS SRM 21 (Division I Level Three)



Problem Statement

    

The students at Byteland Institute of Technology are registering electronically for classes. Registration is open for a predetermined number of time units, and each time unit is assigned a positive number called the goodness. Higher goodness values mean that the network is more likely to be available and responsive during those time units. You may log in at most K times during the registration period. Each login may last a maximum of D time units, and logins must not overlap with each other.

You are given a String[] values. Concatenate the elements of values to create one long string. The ith character of this string represents the goodness value of the ith time unit. The goodness values are given as characters 'a' to 'z', which represent values 1 to 26, respectively. Choose a strategy that maximizes the total goodness of the time units during which you are logged in, and return this total goodness value.

 

Definition

    
Class:ElectiveSystem
Method:maximalGoodness
Parameters:String[], int, int
Returns:int
Method signature:int maximalGoodness(String[] values, int D, int K)
(be sure your method is public)
    
 

Constraints

-values will contain between 1 and 20 elements, inclusive.
-Each element of values will contain between 1 and 50 characters, inclusive.
-Each character in values will be between 'a' and 'z', inclusive.
-D and K will be between 1 and 1000, inclusive.
 

Examples

0)
    
{"acacca"}
4
1
Returns: 10
The goodness values are {1,3,1,3,3,1}. You may only log in once for a maximum of 4 time units, so the best strategy is to log in between time units 1 (0-based) and 4, inclusive. The goodness values during this time interval are: 3+1+3+3=10.
1)
    
{"cab","cca"}
2
2
Returns: 10
The goodness values are {3,1,2,3,3,1}. The two login sessions that maximize the total goodness are {3,3} and the first {3,1}. The total goodness is 3+3+3+1=10.
2)
    
{"abcdefghijkl"}
100
100
Returns: 78
Since you are allowed to log in up to 100 times for up to 100 time units each, you can remain logged in for the entire registration period. The maximal total goodness is therefore 1+2+3+...+12=78.
3)
    
{"yptcsevnuzlsrfjxurpslztlinhddelpitmvaezowjcfjjfgmf","q"}
2
18
Returns: 598
4)
    
{"zzhhhhhh","zz"}
7
2
Returns: 152
Here you can also remain logged in for the entire registration period. One way to do this is to log in between time units 0 and 4, inclusive, and then immediately again between time units 5 and 9, inclusive. Note that you do not have to remain logged in for the entire 7 time unit maximum during each session.

Problem url:

http://www.topcoder.com/stat?c=problem_statement&pm=6796

Problem stats url:

http://www.topcoder.com/tc?module=ProblemDetail&rd=10073&pm=6796

Writer:

zhuzeyuan

Testers:

PabloGilberto , brett1479 , Olexiy

Problem categories:

Dynamic Programming