1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
import java.io.IOException;
import java.util.Scanner;

/**
 * @author khelman
 */
public class kug {

    public static void main(String... args) throws IOException {

        Scanner scanner = new Scanner(System.in);

        int n = scanner.nextInt();

        long[][] c = new long[n][n];

        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                c[i][j] = scanner.nextLong();
            }
        }

        long[][] d = new long[n][n];

        long[][] m_old = new long[n][n];
        long[][] m_new = new long[n][n];

        for (int i = 0; i < n; i++) {
            d[i][i] = c[i][i];
            m_old[i][i] = c[i][i];
        }



        for (int l = 2; l <= n; l++) { //length
            for (int i = 0; i <= n - l; i++) { //start
                //calculating i to i + l - 1  (total length l)
                d[i][i + l - 1] = Long.MAX_VALUE;
                for (int j = 0; j < l; j++) { //gap position
                    long leftCost = 0L;
                    long rightCost = 0L;

                    if (j > 0) {
                        leftCost = d[i][i + j - 1];

                        if (j < l - 1) {
                            //middle gap
                            m_new[i][i + j] = Math.min(Math.min(m_old[i][i + j], m_old[i + 1][i + j]), c[i][i + l - 1]);
                        } else {
                            //right most gap
                            m_new[i][i + j] = Math.min(m_old[i + 1][i + j], c[i][i + l - 1]);
                        }

                    } else {
                        //left most gap
                        m_new[i][i + j] = Math.min(m_old[i][i + j], c[i][i + l - 1]);
                    }

                    if (j < l - 1) {
                        rightCost = d[i + j + 1][i + l - 1];
                    }

                    if (d[i][i + l - 1] > leftCost + rightCost + m_new[i][i + j]) {
                        d[i][i + l - 1] = leftCost + rightCost + m_new[i][i + j];
                    }

                }

                for (int j = 1; j < l; j++) { //split position
                    long leftCost = d[i][i + j - 1];

                    long rightCost = d[i + j][i + l - 1];

                    if (d[i][i + l - 1] > leftCost + rightCost) {
                        d[i][i + l - 1] = leftCost + rightCost;
                    }

                }
            }

            long[][] tmp = m_new;
            m_new = m_old;
            m_old = tmp;
        }

        System.out.println(d[0][n - 1]);

    }

}