题目链接：http://acm.uestc.edu.cn/#/problem/show/1641

题解：
建立n+1个虚拟点0到n，对于询问区间[l,r]，在l-1与r之间连边，边权为C[l][r]
那么能得到该序列的极小询问集合会构成这n+1个点的一个生成树，代价为边权和
证明(?)：
要得到n个位置的值，至少要询问n次
若询问集合构成的图存在回路
那么该回路对应的询问子集中任意一个询问的结果都可以由其它询问得到
故询问集合构成的图有n条边且没有回路
也就是这n+1个点的一个生成树
所以对这n+1个点跑一遍最小生成树即可
时间复杂度：O(n^2)
空间复杂度：O(n^2)

//UESTC 1641

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
const int maxm = 1000010;
int fa[maxn];
struct edge{
    int u, v, w;
    edge(){}
    edge(int u, int v, int w):u(u),v(v),w(w){}
}E[maxm];
int find_set(int x){
    if(x==fa[x]) return x;
    else return fa[x] = find_set(fa[x]);
}
void union_set(int x, int y){
    int fx = find_set(x), fy = find_set(y);
    if(fx!=fy){
        fa[fx]=fy;
    }
}
bool cmp(edge a, edge b){
    return a.w<b.w;
}
int n, x, cnt;

int main()
{
    scanf("%d", &n);
    for(int i=0; i<=n; i++) fa[i]=i;
    cnt = 0;
    for(int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            scanf("%d", &x);
            E[++cnt]={i-1, j, x};
        }
    }
    int ans = 0;
    sort(E+1, E+cnt+1, cmp);
    int edgecnt = 0;
    for(int i=1; i<=cnt; i++){
        int x = find_set(E[i].u), y = find_set(E[i].v);
        if(x != y){
            fa[x] = y;
            ans += E[i].w;
            edgecnt++;
            if(edgecnt==n) break;
        }
    }
    printf("%d\n", ans);
    return 0;
}