Practice Record: TopCoder SRM 654 DIV1
250 SquareScores
Problem Statement
http://community.topcoder.com/stat?c=problem_statement&pm=13694
My Solution
DP: Let's say dpExp[i][j] is the expected value of the postfix run-length of
jth character at the end of substring S[0..i]. At (i+1)th character, if (i+1)th character is same as
ith character, the score is increased by dpExp[i][j]+1. (Imagine constant substring 'aaa' whose expected postfix run-length of 'a' is three and if 4th character is also 'a', the score is increased by four) So you can calculate dpExp[i][j] one by one.
450 SuccessiveSubtraction2
Problem Statement
http://community.topcoder.com/stat?c=problem_statement&pm=13700
My Solution
Inserting two bracket is actually the same as picking two subarray from the origin array and inverse their sign. (Note that the first element is always plus and the second is always minus. You can not include the first and second one in those subarrays.) So you only need to pick up two sub arrays so their sum is maximized. To calculate it in a reasonable order, I pre-calculate the max values of sums of subarray out of [0..i] (first subarray max) and one out of [i..n] (second subarray max). After calculating it, I just iterate all possible 'pivot' elements which sprit the original array into two groups and sum first max and second max to get the total max.
