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
#include <cstdio>
#include <climits>
#include <algorithm>
#include <vector>
#include <set>

using namespace std;

const int maxn = 2001;
int c[maxn][maxn];
int r[maxn][maxn];

struct Cost {
	int value;
	int left, right;

	Cost(int v, int l, int r) : value(v), left(l), right(r) {}
};

bool cost_order(const Cost &a, const Cost &b) {
	return a.value < b.value;
}

vector<Cost> costs;

int currentv[maxn];
int nextv[maxn];


int different_vals(int array[], int imax) {
	/*
	int vals[maxn];
	for (int i = 0; i < maxn; ++i) {
		vals[i] = 0;
	}*/

	set<int> vals;
	for (int i = 0; i < imax; ++i) {
		if (array[i] == 0)
			continue;

		//++vals[array[i]];
		vals.insert(array[i]);
	}

/*	int count = 0;
	for (int i = 0; i < maxn; ++i) {
		if (vals[i] != 0) ++count;
	}

	return count;*/

	return vals.size();
}

int main(int argc, char *argv[]) {

	int n;
	scanf("%d", &n);

	int c;
	for (int i = 0; i < n; ++i) {
		for (int j = i; j < n; ++j) {
			scanf("%d", &c);
			Cost cost {c, i, j};
			costs.push_back(cost);
		}
	}

	sort(costs.begin(), costs.end(), cost_order);

	int maxval = 1;
	long long total_cost = 0;
	for (auto cost : costs) {
		for (int i = 0; i < n; ++i) {
			nextv[i] = currentv[i];
		}

		for (int i = cost.left; i <= cost.right; ++i) {
			nextv[i] += maxval; 
		}

		int cvals = different_vals(currentv, n);
		int nvals = different_vals(nextv, n);
		if (cvals < nvals) {
			total_cost += cost.value;

			for (int i = 0; i < n; ++i) {
				currentv[i] = nextv[i];
			}
		}
		
		for (int i = 0; i < n; ++i) {
			if (currentv[i] >= maxval) {
				maxval = currentv[i] + 1;
			}
		}

		if (nvals == n)
			break;
	}

	printf("%lld\n", total_cost);

	return 0;
}