INOI 2017 Problem 2 - Training INOI 2017, Problem 2, Training
Ash and his Pokemon Pikachu are going on a journey. Ash has planned his route for the journey so that it
passes through N cities, numbered 1, 2, …, N, and in this order.  

When they set out, Pikachu has an initial strength of Sin as well as an experience value (XV) of 0. As they
travel they may increase his strength and experience value in a manner to be described below.
In each city, Ash can choose either to train Pikachu or let Pikachu battle the Gym-leader (but not both). The
Gym-leader in ith city has experience E[i]. If Pikachu enters a city i with strength S and decides to train, then
this increases his strength by the cube of the sum of the digits in his current strength.   

For example, if he
entered a city with a strength of 12, then training will increase his strength to 12 + (1+2)3 = 39. On the other
hand, if he enters city i with strength S and battles the Gym-leader, then this increases his experience value
XV by S*E[i].
Ash wants your help to find out the maximum XV that Pikachu can attain at the end of his journey.    

Input
The first line contains two space separated integers, N and Sin, which are the number of cities, and the
initial strength, respectively.
The second line contains N space separated integers, which correspond to E[1], E[2],..., E[N].

Output
A single integer which is the maximum XV that Pikachu can attain.
Constraints

For all test cases you may assume that:
1 ≤ N ≤ 5000
0 ≤ Sin ≤ 109
0 ≤ E[i] ≤ 104

Subtask 1: For 10% of the score,
N ≤ 20 and Sin = 1
Subtask 2: For further 40% of the score,
E[i] = k for all i
i.e. E[i] is some constant k, for all i
Subtask 3: For further 50% of the score,
No further constraints.  

============================================================================

I managed to solve the first subtask by employing a brute force solution (O(2^n)). But for the second and third subtasks I don't think that a brute force solution will be optimal.
Also, for the second subtask I have a vague idea. Taking X to be the number of trainings, then N-X is the number of battles. By maximizing experience gained  from N-X battles, we might get the answer, but I'm not sure if it's the right way.
I do not have any idea of how to solve the 3rd Subtask without using a brute force algorithm. Help would be appreciated.
Edit: Link to the above question in the IARCS website : https://www.iarcs.org.in/inoi/2017/
Here is how I would approach it. Yes, dynamic programming is a way to solve this problem efficiently. 

A few notations to note before hand :


prefix[k] = sum of all terms from 0 to k ( k included ).
best[k] = max possible XV till term k ( k included )


Algorithm :

 1. prefix[0] = A[i];
 2. best[0] = cubed sum A[i]

 for array A:
    // max ( m,n ) --&gt; max of m and n.
    3. best[i] = max ( cubed sum (prefix[i-1] + A[i]), best[i-1] * A[i]);

 return best[n]. n --&gt; size of array.


In other words, you choose the max value of either including the current strength into sum or by competing.