BZOJ

分析

设 $sum_i$ 表示 $\sum_{j=1}^i[i\text{中有球}]$。显然我们只需要知道所有的 $sum_i$ 就可以知道每个杯子中是否有球了。

考虑到如果询问了 $[i,j]$，那么一旦知道 $sum_{i-1}$ 或 $sum_j$ 中的一个就可以知道另一个。

因此考虑这样一个模型：对于每个区间 $[i,j]$ ，在 $i-1$ 和 $j$ 间连一条边权为 $c_{i,j}$ 的无向边。那么最小生成树就是答案。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;
typedef long long ll;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;

int n,m;
struct edge { int u,v,w; } e[N*N];
bool operator <(edge a,edge b) { return a.w<b.w; }

int f[N];
inline int find(int x) { return x==f[x]?x:f[x]=find(f[x]); }

inline ll kruskal() {
    ll ans=0;
    for (re int i=1;i<=n;++i) f[i]=i;
    sort(e+1,e+m+1);
    for (re int i=1;i<=m;++i) {
        int p=find(e[i].u),q=find(e[i].v);
        if (p^q) ans+=e[i].w,f[p]=q;
    }
    return ans;
}

int main() {
    n=read();
    for (re int i=1;i<=n;++i)
        for (re int j=i;j<=n;++j)
            e[++m]=(edge){i-1,j,read()};
    printf("%lld\n",kruskal());
    return 0;
}