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
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include<cstdio>
#include<iostream>
#include<vector>
#include<climits>
#include<algorithm>
using namespace std;

class Prices
{

private:
	vector<vector<int>> _prices;	

	int Get(int i, int j) {
		return _prices[i][j - i];
	}

public:

	void Set(int i, int j, int value) {
		if (j == 0) {
			_prices.push_back(vector<int>());
		}
		_prices[i].push_back(value);
	}

	int Get(pair<int, int> segment) {
		return Get(segment.first, segment.second-1);
	}
	
};

Prices * prices;
int n;
long long int ***minprices;


bool isEmpty(pair<int, int> inputSegment) {
	if (inputSegment.first < inputSegment.second) return false;
	return true;
}

long long int GiveMinimum(pair<int, int> inputSegment, int currentIndex) {
	long long int minimum = LLONG_MAX;
	pair<int, int> bieremy, zostaje;
	if (currentIndex == n) return 0;
	if (minprices[inputSegment.first][inputSegment.second][currentIndex] == 0)  {
		if (isEmpty(inputSegment)) {
			for (int i = 0; i < currentIndex; i++) {
				minimum = min(minimum, GiveMinimum(make_pair(i, currentIndex + 1), currentIndex));
			}
			for (int i = currentIndex; i < n; i++) {
				minimum = min(minimum, GiveMinimum(make_pair(currentIndex, i + 1), currentIndex));
			} 
		}
		else {
			long long int tmp;
			//2 - use only previous segments to conclude about currentIndex
			if (currentIndex + 1 < inputSegment.second)  {
				for (int i = 0; i < currentIndex + 1; i++) {
					bieremy = make_pair(i, currentIndex + 1);
					tmp = GiveMinimum(inputSegment, currentIndex + 1) + prices->Get(bieremy);
					if (tmp < minimum) {
						minimum = tmp;
					}
				}
			}	
			//1 - use inputSegment + next segment to conclude about currentIndex
			zostaje = make_pair(currentIndex + 1, inputSegment.second);
			tmp = GiveMinimum(zostaje, currentIndex + 1) + prices->Get(inputSegment);
			if (tmp < minimum) {
				minimum = tmp;
			}
		}
		minprices[inputSegment.first][inputSegment.second][currentIndex] = minimum;
	}

	return minprices[inputSegment.first][inputSegment.second][currentIndex];
}

int main() {

	int x;
	scanf("%d", &n);
	prices = new Prices();

	minprices = new long long int**[n+1];
	for (int x = 0; x < n + 1; ++x) {
		minprices[x] = new long long int*[n + 1];
		for (int y = 0; y < n + 1; ++y) {
			minprices[x][y] = new long long int[n + 1];
			for (int z = 0; z < n + 1; ++z) { 
				minprices[x][y][z] = 0;
			}
		}
	}

	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n - i; j++) {
			scanf("%d", &x);
			prices->Set(i, j, x);
		}
	}

	printf("%lld\n", GiveMinimum(make_pair(0, 0), 0));

}