Netrpeljivost

시간 제한1.5초메모리 제한1024 MB

요약

2의 거듭제곱 수의 손님이 완전 이진 트리의 리프로 놓여 있고, 각 노드에서 자식을 임의로 바꿀 수 있을 때 이웃한 손님 사이 비용 합의 최솟값을 구합니다.

난이도: 보통10점 중 6점
유형: 동적 계획법, 트리, 그리디, 분할 정복
정답자: 아직 제출이 없습니다

문제

Ponoć se približavala, valjalo se požuriti. Nakon što je Margarita uspješno pozdravila sve goste, oni su nesmetano zasjeli za dugačak stol. Goste možemo označiti brojevima od $1$ do $N$ , točno onim redom kojim su zasjeli na stol. Iz nepoznatih razloga, broj gostiju na velikom balu kod Sotone uvijek je potencija broja $2$ .

No, Margarita se sada nalazi u problemu, jer između svakog para gostiju vlada određena netrpeljivost koju možemo označiti nenegativnim brojem. Netrpeljivost između gostiju $i$ te $j$ možemo označiti kao $netrp(i, j)$ . Uvijek vrijedi $netrp(i, j) = netrp(j, i)$ te $netrp(i, i) = 0$ .

Kako su se gosti već (ne)ugodno smjestili, Margarita ne smije drastično mijenjati njihov poredak. Gosti zapravo ni ne znaju da se nalaze u listovima velikog Sotoninog potpunog binarnog stabla, popularno zvanom VSPBS, koje je prikazano na slici u slučaju $N = 4$ .



(a) Slika 1: stablo na početku	(b) Slika 2: stablo nakon operacije

Margarita može odabrati neki čvor, i u jednom potezu zamijeniti lijevo i desno dijete toga čvora, time promijenivši poredak gostiju koji se nalaze u pripadajućim listovima. Prikazano je stanje stabla, a time i stola, nakon što Margarita napravi jedan potez nad korijenom stabla. Margarita može napraviti prozivoljan broj poteza nad proizvoljnim čvorovima.

Ukupna netrpeljivost stola definira se kao zbroj netrpeljivosti susjeda za stolom. Pomozite Margariti odrediti najmanju moguću netrpeljivost stola koju može postići!

입력

U prvom je retku prirodan broj $N$ , broj gostiju.

U i-tom od sljedećih $N$ redaka nalaze se redom brojevi $netrp(i, j)$ koji zadovoljavaju gornja svojstva.

출력

Potrebno je ispisati traženi broj iz zadatka.

힌트

Pojašnjenje probnih primjera: U drugom primjeru, jedan od mogućih rasporeda koji postiže najmanju netrpeljivost je 2 1 4 3.

예제3

예제 1
입력
```
2
0 2
2 0
```
예상 출력
```
2
```
예제 2
입력
```
4
0 2 3 1
2 0 4 5
3 4 0 3
1 5 3 0
```
예상 출력
```
6
```

예제 3

입력

8
0 2 5 8 5 9 2 6
2 0 8 4 3 7 5 3
5 8 0 3 8 4 3 3
8 4 3 0 2 2 7 7
5 3 8 2 0 7 3 3
9 7 4 2 7 0 6 7
2 5 3 7 3 6 0 4
6 3 3 7 3 7 4 0

예상 출력