[PA2014]Kuglarz
Time Limit: 20 Sec Memory Limit: 128 MB
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
Orz!!! Orz!!! Orz!!! Orz!!! Orz!!! Orz!!! Orz!!!
Orz!!! Orz!!! Orz!!! Orz!!! Orz!!! Orz!!! Orz!!!
太tm强了，真的太强了，我又一次见识了人类智慧。。。。
我们来想一想怎么才可以知道一个杯子下面是否有球。。。。。。
举个栗子：
（1） （2） （3） （4） （5）
如果我们知道1到5的奇偶性和2到5的奇偶性不一样的话，显然1是有球的，反之没有。
我们要确定每个杯子有没有球，那么就变成了我们要求两个区间的奇偶性，他们唯一的差别就是是否只差你询问的这个杯子的情况。
那么我们再思考一下，显然区间([1,5] 等价于 [1，2]和[3,5])，对吧？
也就是说，如果我们知道了两个相邻子区间的情况，就等价于知道这个两个合并的大区间的情况。
同理，我们也可以知道一个大区间和他的一个子区间（必须有一个端点一样），就可以知道另一个。
那么对于每一个区间，我们如果知道他，就把他用并查集连起来。
那么我们再考虑另一个问题，怎么表示一个区间，我的方法是记录他们之间的间隙的编号，以每个间隙为一个点，显然，n个杯子有n+1个点。
然而另一个妙妙的事情出现了，考虑什么叫做知道这个区间。他的意义是什么（想一想~）我们如何表示的知道这个区间。
我们把两个区间端点连起来表示知道这个区间，对吧?
那么什么叫知道所有区间？
所有区间端点都是联通的。
好，问题变成了这样：
有(n)个点，你可以连接任意两个点，连接每两个点都有对应的代价，请问，怎样用最小的代价将他们全部联通？？？
喵喵喵~~~
有(n)个点，有(n^2)左右的边，每个边的边权已知，问最小的代价将他们联通。
你好，我是最小生成树。
#include<bits/stdc++.h>
using namespace std;
const int maxn = 2e3 + 5;
struct lpl{
int a, b, dis;
bool operator < (const lpl &x)const{
return dis < x.dis;
}
}lin;
int n, len, cnt, aaa, bbb, fa[maxn];
long long ans;
vector<lpl> edge;
int find(int t){ return (fa[t] == t) ? t : (fa[t] = find(fa[t])); }
inline void connect(int a, int b){a = find(a); b = find(b); fa[a] = b;}
inline void putit()
{
scanf("%d", &n);
for(int i = 1; i <= n; ++i)
for(int j = i; j <= n; ++j){
scanf("%d", &lin.dis); lin.a = i; lin.b = j + 1;
edge.push_back(lin);
}
}
inline void workk()
{
sort(edge.begin(), edge.end()); len = edge.size() - 1;
for(int i = 1; i < maxn; ++i) fa[i] = i;
for(int i = 0; i <= len; ++i){
aaa = find(edge[i].a), bbb = find(edge[i].b);
if(aaa == bbb) continue;
connect(aaa, bbb); cnt++; ans += edge[i].dis;
if(cnt == n) break;
}
}
int main()
{
putit();
workk();
printf("%lld", ans);
return 0;
}