[文章目录]
Description
魔术师的桌子上有n个杯子排成一行，编号为1,2,…,n，其中某些杯子底下藏有一个小球，如果你准确地猜出是哪些杯子，你就可以获得奖品。花费c_ij元，魔术师就会告诉你杯子i,i+1,…,j底下藏有球的总数的奇偶性。采取最优的询问策略，你至少需要花费多少元，才能保证猜出哪些杯子底下藏着球？n<=2000
观察样例，发现每个所选区间都至少包含一个别的区间进行加减不可得到的单点。那么说明肯定的选n个区间，并且这n个区间不能存在可以由其他区间的加减得到的区间。
将区间的间隔当成节点，发现有n+1个节点，区间的花费想成连接间隔的边的边权。因为如果一个区间能够被其他区间推出的话一定存在一个环，发现问题变成了求一颗最小生成树。
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n,tot,fa[2100];
struct node
{
int x,y,d;
}a[4001000];
long long ans;
bool cmp(node x,node y) {return x.d<y.d; }
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
int main()
{
scanf("%d",&n); int x,y;
for(int i=1;i<=n+1;++i) fa[i]=i;
for(int i=1;i<=n;++i)
{
for(int j=i;j<=n;++j)
{
scanf("%d",&x);
a[++tot].x=i;
a[tot].y=j+1;
a[tot].d=x;
}
}
sort(a+1,a+tot+1,cmp);
for(int i=1;i<=tot;++i)
{
x=find(a[i].x); y=find(a[i].y);
if(x!=y)
{
ans+=a[i].d;
fa[x]=y;
}
}
printf("%lld",ans);
return 0;
}