题意
有 \(n\) 个杯子，会告诉你每一个区间 \(i\) ， \(j\) 需要的花费，从而得知这一区间内所有小球总和的奇偶性，因为我们知道每一个杯子下的小球只有一个或两个，因此这道问题便可以通过最短路的方式来做了
做法
在得到两个共端点的区间奇偶性后，就可以得到非共端点之间的奇偶性，例如，你知道了一到三号和一到四号的奇偶性，显而易见你就可以得到四号的奇偶性，所以，对于每一个 \(c\) ，我们可以建一条边，然后跑最小生成树即可。
如何建边呢？
很显然我们是不能单纯从 \(i\) 指向 \(j\) 的，比如 \(i=j\) 的边就作废了，所以建边策略为从 \(i\) 建一条向 \(j+1\) 的边，将端点数加一，再跑树。
最小生成树
常见的做法有两种， \(Prim\) 和 \(Kruskal\) 。这里介绍的是后者。
将一个连通块当做一个集合。首先将所有的边按从小到大顺序排序，并认为每一个点都是孤立的，分属于 \(n\) 个独立的集合。然后按顺序枚举每一条边。如果这条边连接着两个不同的集合，那么就把这条边加入最小生成树，这两个不同的集合就合并成了一个集合；如果这条边连接的两个点属于同一集合，就跳过。直到选取了 \(n-1\) 条边为止。
简单来说， \(Kruskal\) 每次都选择一条最小的边，而且这条边的两个顶点分属于两个不同的集合。将选取的这条边加入最小生成树，并且合并集合。
代码
#include<bits/stdc++.h>
using namespace std;
int n,vis[2002],sum,tot,fa[2002];
long long ans;
struct node{//邻接表
int from,to,w;
}a[2001001];
void add(int q,int m,int bq){//加边
a[++tot].to=m;
a[tot].from=q;
a[tot].w=bq;
}
int find(int x){//判断联通块
if(!fa[x])return x;
return fa[x]=find(fa[x]);//查询顺便更新该位置标志，会节省时间
}
bool cmp(node x,node y){//按边权排序
return x.w<y.w;
}
inline int read(){
int s=0;
char ch=getchar();
while(ch<‘0‘||ch>‘9‘)ch=getchar();
while(ch>=‘0‘&&ch<=‘9‘)s=(s<<3)+(s<<1)+ch-‘0‘,ch=getchar();
return s;
}
int main()
{
n=read();
int x;
for(int i=1;i<=n;i++){
for(int j=1;j<=n-i+1;j++){
x=read();
add(i,i+j,x);
}
}
sort(a+1,a+tot+1,cmp);
for(int i=1;i<=tot;i++){
int xx=find(a[i].from),yy=find(a[i].to);
if(xx==yy)continue;//已为同一联通块
if(xx!=yy){
sum++;//连边 ，边数加一
fa[xx]=yy;//合并
ans=(long long)ans+a[i].w;
}
if(sum==n)break;//已建成最小生成树
}
cout<<ans<<endl;
return 0;
}