P5994 [PA 2014] Kuglarz

There are $n$ cups in a row on the magician’s table, numbered $1,2,\ldots,n$. Some of the cups have a small ball hidden under them. If you can correctly guess which cups have balls under them, you will win a prize. By paying $c_{ij}$ yuan, the magician will tell you the parity (odd or even) of the total number of balls hidden under cups $i,i+1,\ldots,j$. Using an optimal questioning strategy, what is the minimum amount of money you must pay to guarantee that you can determine exactly which cups have balls under them?

The first line contains an integer $n$. Line $i+1$ ($1\le i\le n$) contains $n+1-i$ integers, giving the cost of each possible query. Among them, $c_{ij}$ (the cost to query the interval $[i,j]$, $1\le i\le j\le n$) is the $(j+1-i)$-th number on line $i+1$.

Output one integer, the minimum total cost.

For $100\%$ of the testdata, $1\le n\le 2\times 10^3$, $1\le c_{ij}\le 10^9$. Translated by ChatGPT 5