【bzoj3714】[PA2014]Kuglarz

2014年9月28日2,2235

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

题解

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

 

  • wulala2014年10月15日 下午3:50 回复

    差分约束啊就是

    #1  
    • Chenyao2014年10月15日 下午4:12 回复

      Orzzzzzzz求解释

      #11
      • wulala2014年10月15日 下午5:04 回复

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

        #12
        • Chenyao2014年10月16日 上午9:09 回复

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

          #13
          • wulala2014年10月16日 上午9:15

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

            #14