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
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

struct hint
{
	int i, j;
	int c;
	int r; // r = j - i + 1
	bool u;
	hint() : u(false) {}
	bool operator<(const hint &h) const
	{
		if (c < h.c)
			return true;

		return false;
	}
};

ostream & operator<<(ostream &str, const hint &h)
{
	return str << "(" << h.i << ";" << h.j << ") c=" << h.c << " r=" << h.r << "\n";
}

int main(int argc, char ** argv)
{
	cin.sync_with_stdio(false);
	int n;
	cin >> n;
	int Nh = (static_cast<double>(1+n)/2.0)*n;
	vector<hint> hints(Nh);
	int check_sum[2001] = { 0 };
	bool check[2001] = { false };
	vector<hint>::iterator it = hints.begin();
	for (int i = 1; i <= n; ++i)
	{
		for (int j = i; j <= n; ++j, ++it)
		{
			(*it).i = i;
			(*it).j = j;
			(*it).r = (*it).j - (*it).i;
			cin >> (*it).c;
		}
	}
	
	sort(hints.begin(),hints.end());
	long long price = 0;

	while (check_sum[n] < n)
	{
		bool changed = false;
		for (int k = 0; k < Nh && changed == false; ++k)
		{
			if (hints[k].u == false)
			{
				int w = check_sum[hints[k].j] - check_sum[hints[k].i-1]; 
				if (w == hints[k].r)
				{
					hints[k].u = true;
					price += hints[k].c;
					bool checking = false;
					for (int m = hints[k].i; m <= n; ++m)
					{
						if (check[m] == false && checking == false)
						{
							check[m] = true;
							checking = true;
						}

						if (checking)
							++check_sum[m];
							
					}
					changed = true;
				}
			}
		}
	}
	cout << price << "\n";
	return 0;
}