題目描述

小明和朋友們?cè)诤娇詹┪镳^玩捉迷藏，現(xiàn)在有N間房間連成一排，編號(hào)為1,2,…,N，其中某些房間里面有1個(gè)人（且不會(huì)超過(guò)1個(gè)），其它房間沒(méi)有人。小明可以使用Cij個(gè)航天紀(jì)念幣讓博物館管理員告訴他i,i+1,…,j這些房子里人員總數(shù)的奇偶性。采取最優(yōu)的詢問(wèn)策略，小明至少需要使用多少紀(jì)念幣，才能準(zhǔn)確找到哪些房子里有人（能夠處理人員任意分布的情形）？

輸入說(shuō)明

第一行是一個(gè)整數(shù)N(1≤N≤2000)。 接下來(lái)N行，第i行有（N-i+1）個(gè)數(shù)，代表Cij≤10^9，1≤i≤j≤N。

輸出說(shuō)明

輸出一個(gè)整數(shù)，表示最少使用的紀(jì)念幣個(gè)數(shù)。

輸入樣例?

5

1 2 3 4 5

4 3 2 1

3 4 5

2 1

5

輸出樣例

7

確定每個(gè)房間是否有人等價(jià)于確定所有的前綴的奇偶性。

如果知道 ? ( i-1?, i?],?? ?的奇偶性，? 即知道前綴i-1和前綴i 的關(guān)系：

1. 奇偶相同，i 沒(méi)有人。

2. 奇偶不同，i有人。

?

我們需要知道? ( 0 , 1 ], ( 1 , 2 ],? ( 2 , 3 ], ......? ( N-1 , N ] 的奇偶性，實(shí)際上是要連通

0，1，2，3，......, N-1, N? 這N+1個(gè)點(diǎn)。

?

對(duì)于區(qū)間?[?L , r ] 實(shí)際上就是連通了前綴L? 1 和前綴r。

所以我們的目的是： 選擇N個(gè)最小費(fèi)用的區(qū)間[ L , r ]，連通

0，1，2，3，......, N-1, N? 這N+1個(gè)點(diǎn)。即求一個(gè)最小生成樹，用kruskal算法