「BZOJ3714」[PA2014] Kuglarz

2014年9月28日2,9025

Description

魔术师的桌子上有n个杯子排成一行,编号为1,2,…,n,其中某些杯子底下藏有一个小球,如果你准确地猜出是哪些杯子,你就可以获得奖品。花费c_ij元,魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。
采取最优的询问策略,你至少需要花费多少元,才能保证猜出哪些杯子底下藏着球?

Input

第一行一个整数n(1<=n<=2000)。
第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个数。

Output

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

Sample Input

5
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5

Sample Output

7

题解

最小生成树。。。不要问我为什么 (跪在电脑前)

 

说点什么

提醒
avatar
wulala

差分约束啊就是

Chenyao

Orzzzzzzz求解释

wulala

去把bzoj1202做了吧,就知道为什么了

Chenyao

我去做了…然后..觉得相似地方好像就用到前缀和的性质,然后蒟蒻求教此题怎么差分约束

wulala

那题不是要用到并查集吗QAQ,这个题也是弄一个前缀和(异或和),然后就会有n(n+1)/2个等式,全是等式就代表这个图中任意一对点之间的所有路径长度是相同的。每次魔术师可以知道任意两个点之间的路径长度,所以就是最小生成树了,这东西就是差分约束的一种情况啊,每个等式a = b可以看做联立 a >= b和 a <= b