SkewTree

Code

public class SkewTree

{

    int[] probs;

    int[][] best;

    int getAccess(int i1, int i2) {

        int total=0;

        for (int i=i1; i <= i2; i++) total += probs[i];

        return total;

    }

    int getBest(int i1, int i2) {

        if(i1 > i2) return 0;

        if(best[i1][i2]!=0) return best[i1][i2];

        int val=Integer.MAX_VALUE;

        for (int root=i1; root <= i2; root++) {

            int thisVal = getBest(i1,root-1) + getBest(root+1,i2);

            if(thisVal < val) val = thisVal;

        }

        val += getAccess(i1,i2);

        best[i1][i2] = val;

        return val;

    }

    public int bestScore(int[] values, int[] _probs) {

        probs = _probs; best = new int[50][50];

        int n=values.length;

        for (int i=0; i < n; i++) {

            for (int j=i+1; j < n; j++) {

                if (values[i] > values[j]) {

                    int tv = values[j]; values[j] = values[i]; values[i] = tv;

                    int tp = probs[j]; probs[j] = probs[i]; probs[i] = tp;

                }

            }

        }

        return getBest(0, n-1);

    }

}

Explanation

values와 probs를 정렬한 후 getBest() 함수를 돌려 가장 적은 확률값을 지닌 트리를 구한다.

best[][] 배열은 각 노드나 하위 트리(subtree)의 확률 값을 저장하는데 사용하여 계산과정의 중복을 방지한다.

thisVal = getBest() + gestBest() 는 leaf 나 subtree의 값을 구하여 저장한다.

getAccess()는 해당 i1,i2의 확률값을 구한다. 해당 노드부터 확률값을 구하게 되므로 p*(d-1) 공식을 사용한 것과 같은 결과를 얻는다.

References

http://community.topcoder.com/stat?c=problem_solution&cr=262936&rd=4497&pm=1641