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

*j*th character at the end of substring S[0..i]. At (i+1)th character, if (i+1)th character is same as

*i*th 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.

## No comments:

## Post a Comment