本文共 1818 字，大约阅读时间需要 6 分钟。

$$\mathrm{Kuglarz}$$

题目链接：

题目

魔术师的桌子上有 $n$ 个杯子排成一行，编号为 $1,2,\dots ,n$ ，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。

花费 $c_{ij}$ 元，魔术师就会告诉你杯子 $i,i+1,\dots ,j$ 底下藏有球的总数的奇偶性。

采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？

输入

第一行一个整数 $n$ 。

第 $i+1$ 行（ $1\le i\le n$ ）有 $n+1-i$ 个整数，表示每一种询问所需的花费。

其中 $c_{ij}$ （对区间 $[i,j]$ 进行询问的费用， $1\le i\le j\le n$ ）为第 $i+1$ 行第 $j+1-i$ 个数。

输出

输出一个整数，表示最少花费。

样例输入

51 2 3 4 54 3 2 13 4 52 15

样例输出

7

数据范围

对于 $100\%$ 的数据， $1\le n\le 2\times 10^3$ ， $1\le c_{ij}\le 10^9$ 。

思路

这道题是一道最小生成树。

我们可以发现，我们要确定 $i$ 里面有没有东西，有两种方法：

1. 直接看 $(i,i)$
2. 看 $(i,j)$ 和 $(i+1,j)$

我们可以把点变成边权， $i$ 变成 $i-1$ 到 $i$ 的一条边。

那就变成了最小生成树。

有一点要注意的是， $ans$ 要开 $longlong$ 。

代码

#include
   
    #include
    
     using namespace std;const int N = 2001;struct node {   	int x, from, to;}e[N * N * 2];int n, x, fa[N], KK, num;long long ans;void add(int x, int y, int z) {   //建图	e[++KK] = (node){   z, y, x};}bool cmp(node x, node y) {   //按权值排序	return x.x < y.x;}int find(int now) {   //并查集	if (fa[now] == now) return now;	return fa[now] = find(fa[now]);}int main() {   	scanf("%d", &n);//读入		for (int i = 1; i <= n; i++) {   		fa[i] = i;//初始化		for (int j = i; j <= n; j++) {   			scanf("%d", &x);//读入			add(i - 1, j, x);//建图		}	}		sort(e + 1, e + KK + 1, cmp);//按边权排序		for (int i = 1; i <= KK; i++) {   //最小生成树		int X = find(e[i].from), Y = find(e[i].to);		if (X != Y) {   			fa[X] = Y;			ans += (long long)e[i].x;//记录答案			num++;			if (num == n) break;		}	}		printf("%lld", ans);//输出		return 0;}