a bit of uva: UVa 10688 - The Poor Giant

Problem Statement:
UVa 10688 - The Poor Giant

Summary:
There are \(N\) apples, and each apples have weight \(K+1, K+2, \ldots, K+N\). There is exactly one apple which is "sweet", and all other apples' taste is measured against the sweet apple: an apple is "bitter" iff it weighs less than sweet apple, otherwise it is a "sour" apple. For a sequence of apples, we have a function \(C(\{a_i\}, k) = \text{minimum total weight of apples eaten before encountering } a_k\), and we want to minimize \(S = \sum_{k=1}^{N} C(\{a_i\}, k) \).

Solution:
Rather than trying all possible sequences and simulating the eating process one by one to arrive at S (which has an exponential complexity btw), we can solve this problem by breaking it into a smaller sub problems by recursion. Furthermore, this problem exhibits an optimal substructure property, as will be clear once we have derived the recursive relationship.

Suppose we have \(M(L,R)\) which is the minimum total weight of apples required for all \(k = L \ldots R\). Let's say we choose \(a_i\) (\(L \leq i \leq R\)) to be eaten first. If \(a_i\) is the sweet apple, then the simulation will terminate. Otherwise, \(a_i\) is not a sweet apple, hence it can be sour or bitter, then we need to find both \(M(L,i-1)\) and \(M(i+1, R)\) to cover both cases. We will end up with the following recursion: \(M(L,R) = min_{L\leq i \leq R} \{ (R-L+1)a_i + M(L,i-1) + M(i+1,R) \}\).

Since there are a lot of overlapping subproblems, we can memoize the results based on the parameter \(L\) and \(R\). This will cut down the running time to \(O(N^3)\).

Implementation in C++:

int dp[503][503];
int a[503];
int rec(int L, int R){
    if(R <= L) return 0;
    if(R-L == 1) return a[L]*2;
    if(R-L == 2) return a[L+1]*3;
    if(dp[L][R] != -1) return dp[L][R];
    int ret = MAXINT;
    for(int i=L; i<= R; ++i){
        ret = min(a[i]*(R-L+1) + rec(L,i-1) + rec(i+1,R), ret);
    }
    dp[L][R] = ret;
    return ret;
}