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
#include <iostream>
#include <limits>
using namespace std;

const int MAX = 2000;
int arrayc[MAX][MAX];
int cost[MAX][MAX];

int main() {
  int n;
  cin >> n;
  for(int i=0; i<n; ++i)
    for(int j=i; j<n; ++j)
      cin >> arrayc[i][j];

  //koszt odkrycia kubka jest znany
  for(int i=0; i<n; ++i) cost[i][i] = arrayc[i][i];

  for(int k=1; k+1 <= n; ++k)  //rozmiar przedziału to k+1
    for(int i=0; i+k < n; ++i) {  //początek przedziału
      int j = i+k;  //koniec przedziału
      //rozważam przedział [i,j]
      int tempCost = numeric_limits<int>::max();
      //dzielę go na [a,b], [c,d], gdzie
      //[a,b] jest w pełni znany
      //[c,d] może przecinać [a,b], wtedy ma składową znaną
      int a = i;
      int d = j;
      for(int b=j-1; a <= b; --b) {
	int c = b+1;  //[c,d] nie przecina [a,b]
	int val = cost[a][b] + cost[c][d];
	if(val < tempCost) tempCost = val;

	//[c,d] przecina [a,b]
	//minimum arrayc[c][d]
	--c;  //c=b
	int min = arrayc[c][d];
	for(--c; c >= a; --c)
	  if(arrayc[c][d] < min) min = arrayc[c][d];

	int val2 = 0;
	//gdy przedział [b+1,d] co najmniej 2 elementowy
	if(d-b >= 2) {
	  //mniejszy z kosztów [b+2,d], [b+1,d-1]
	  if(cost[b+2][d] < cost[b+1][d-1]) val2 = cost[b+2][d];
	  else val2 = cost[b+1][d-1];
	}
	val = cost[a][b] + min + val2;
	if(val < tempCost) tempCost = val;
      }

      int b = j;
      int c = i;
      for(int a=i+1; a <= b; ++a) {
	int d = a-1;
	int val = cost[a][b] + cost[c][d];
	if(val < tempCost) tempCost = val;

	++d;
	int min = arrayc[c][d];
	for(++d; d<=b; ++d)
	  if(arrayc[c][d] < min) min = arrayc[c][d];

	int val2 = 0;
	//gdy przedział [c,a-1] co najmniej 2 elementowy
	if(a-c >= 2) {
	  //mniejszy z kosztów [c,a-2], [c+1,a-1]
	  if(cost[c][a-2] < cost[c+1][a-1]) val2 = cost[c][a-2];
	  else val2 = cost[c+1][a-1];
	}
	val = cost[a][b] + min + val2;
	if(val < tempCost) tempCost = val;
      }

      cost[i][j] = tempCost;
    }

  cout << cost[0][n-1] << endl;
}