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
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class kug {

    private static int[][] costs;

    public static void main(final String[] args) {
        final BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        try {
            int cups = Integer.parseInt(reader.readLine());
            costs = new int[cups][cups];
            for (int i = 0; i < cups; i++) {
                final String[] line = reader.readLine().trim().split("\\s+");
                int[] row = new int[cups];
                for (int j = 0; j < line.length; j++) {
                    row[j] = Integer.parseInt(line[j]);
                }
                costs[i] = row;
            }
            System.out.println(costSubTable(0, cups - 1) / 2);
        } catch (IOException e) {
            e.printStackTrace();
        }
        System.exit(0);
    }

    public static int costSubTable(int from, int to) {
        if (from == to) {
            return cost(from, to);
        } else if (to - from == 1) {

            return cost(from, to) + Math.min(cost(from, from), cost(to, to));
        } else if (((to - from + 1) % 2) == 1) //nieparzyste
        {
            int costAll = cost(from, to);

            int res = cost(from, from) + costSubTable(from + 1, to);
            res = Math.min(res, costSubTable(from, to - 1) + cost(to, to));
            for (int i = from + 1; i + 1 < to; i++) {
                res = Math.min(res, costSubTable(from, i) + cost(i + 1, i + 1) + costSubTable(i + 2, to));
            }
            return costAll + res;
        } else {      //parzyste
            final int mid = (to + from) / 2;
            return costSubTable(from, mid) + costSubTable(mid + 1, to);
        }
    }

    public static int cost(int i, int j) {
        return costs[i][j - i];
    }
}