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

$$\mathrm{C}\mathrm{h}\mathrm{a}\mathrm{r}\mathrm{m}\mathrm{e}\mathrm{r}--\mathrm{v}\mathrm{i}\mathrm{v}$$

题目链接：

题目背景

viv is a charmer…QwQ

题目

Loi54 的 viv 有另一个身份----魔♂术♂师,今天他要变一个魔♂术，但是， viv 找不到他的魔法球了。一定是调皮的 dc 把球藏了起来。 viv 找到了 dc ，没想到腹黑的 dc 不光不交出 viv 魔法球，还向 viv 索要赎金。

作为一个安静的美男子， viv 不想用暴♂力解决此事，再者 dc 还是 viv 的同学，所以 viv 忍气吞声，准备花 RMB 赎回自己的魔法球。

dc 的服务态度“良♂好”，给出了详细的“询问”价格表。

价格表的形式如下：

（ dc 把 viv 的魔法球放在一个区间内（ $[1,n]$ ）的一个位置上）

$C_{ij}$ ： 代表询问 $[I,j]$ 这个区间球的数量的奇偶性要付多少钱。

Viv 没有多少钱，所以 viv 决定采取最优策略，花最少的钱来找出自己的球。

但是 Viv 不光是穷 X ，还是个蒟蒻，怎么可能找出最优策略，机智的 viv 想到了机智的你们….

Viv ：“求帮忙….QwQ”

输入

第一行一个整数 $n$ 。

第 $i+1$ 行 $(1<=i<=n)$ 有 $n+1-i$ 个整数，表示每一种询问所需的花费。其中 $c_{ij}$ （对区间 $[i,j]$ 进行询问的费用， $1<=i<=j<=n,1<=c_{ij}<=10^9$ ）为第 $i+1$ 行第 $j+1-i$ 个数。

输出

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

样例输入

51 2 3 4 54 3 2 13 4 52 15

样例输出

7

数据范围

$30\%:n<=50$

$60\%:n<=500$

$100\%:n<=1600$ （由于无法传输大文件，所以只能这么小了，我是不是太良心了…）

思路

这道题其实和是同一个道理，就也是最小生成树。

我才发现最小生成树不用双向建边。。。

害，我还是太弱了。

代码

#include
   
    #include
    
     #include
     
      using namespace std;const int N = 1601;struct node {   	int x, to, nxt;}e[N * N * 2];int n, x, KK, dis[N], le[N];bool in[N];long long ans;void add(int x, int y, int z) {   	e[++KK] = (node){   z, y, le[x]}; le[x] = KK;	e[++KK] = (node){   z, x, le[y]}; le[y] = KK;}bool cmp(node x, node y) {   	return x.x < y.x;}int main() {   	scanf("%d", &n);		for (int i = 1; i <= n; i++)		for (int j = i; j <= n; j++) {   			scanf("%d", &x);			add(i, j + 1, x);		}		memset(dis, 0x7f, sizeof(dis));	dis[1] = 0;	for (int i = 1; i <= n; i++) {   		int minx, minn = 2147483647;		for (int j = 1; j <= n; j++)			if (minn > dis[j] && !in[j]) {   				minn = dis[j];				minx = j;			}		ans += (long long)minn;		in[minx] = 1;		for (int j = le[minx]; j; j = e[j].nxt)			if (!in[e[j].to] && dis[e[j].to] > e[j].x)				dis[e[j].to] = e[j].x;	}		printf("%lld", ans);		return 0;}