Problem Link: CodeChef: Practical coding for everyone
Solution Link: CodeChef: Practical coding for everyone
The strategy used (dynamic programming):
dp[i][numberOfTrains]=maxstrength;
dp[i][0]=dp[i-1][0]+s[0]*e[i];
dp[i][j]=max(dp[i-1][j]+s[j]*e[i],dp[i-1][j-1])
dp[i][any j greater than i]=0
answer is max from dp[n-1][0] to dp[n-1][n]
Here, s[i]=strength after i training
e[i]=experience at i city