首页 > 代码库 > BZOJ3714: [PA2014]Kuglarz
BZOJ3714: [PA2014]Kuglarz
3714: [PA2014]Kuglarz
Time Limit: 20 Sec Memory Limit: 128 MBSubmit: 131 Solved: 87
[Submit][Status]
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
1 2 3 4 5
4 3 2 1
3 4 5
2 1
5
Sample Output
7
HINT
Source
鸣谢Jcvb
题解：
真是一道好题！
zrts：
如果知道 i..j 之间奇偶性的话，实际上知道的是 sum[j]-sum[i-1]的奇偶性（sum为前缀和）。
可以用扩展域的并查集维护任意两个sum[i]之间的差值。
有了这个结论，如果全部知道哪些杯底有球，就需要所有的sum之间的关系已知，也就是并查集中所有点都在一个集合中，是一棵树。
所以遍转化成了最小生成树问题。
orzzz
代码：
1 #include<cstdio> 2 3 #include<cstdlib> 4 5 #include<cmath> 6 7 #include<cstring> 8 9 #include<algorithm>10 11 #include<iostream>12 13 #include<vector>14 15 #include<map>16 17 #include<set>18 19 #include<queue>20 21 #include<string>22 23 #define inf 100000000024 25 #define maxn 200526 27 #define maxm 500+10028 29 #define eps 1e-1030 31 #define ll long long32 33 #define pa pair<int,int>34 35 #define for0(i,n) for(int i=0;i<=(n);i++)36 37 #define for1(i,n) for(int i=1;i<=(n);i++)38 39 #define for2(i,x,y) for(int i=(x);i<=(y);i++)40 41 #define for3(i,x,y) for(int i=(x);i>=(y);i--)42 43 #define mod 100000000744 45 using namespace std;46 47 inline int read()48 49 {50 51 int x=0,f=1;char ch=getchar();52 53 while(ch<‘0‘||ch>‘9‘){if(ch==‘-‘)f=-1;ch=getchar();}54 55 while(ch>=‘0‘&&ch<=‘9‘){x=10*x+ch-‘0‘;ch=getchar();}56 57 return x*f;58 59 }60 struct rec{int x,y,w;}e[maxn*maxn];61 int n,tot,fa[maxn];62 ll ans=0;63 inline int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}64 inline bool cmp(rec a,rec b)65 {66 return a.w<b.w;67 }68 69 int main()70 71 {72 73 freopen("input.txt","r",stdin);74 75 freopen("output.txt","w",stdout);76 77 n=read();78 for1(i,n)79 for1(j,n+1-i)80 e[++tot].x=i-1,e[tot].y=i+j-1,e[tot].w=read();81 sort(e+1,e+tot+1,cmp);82 for0(i,n)fa[i]=i;83 int j=1;84 for1(i,n)85 {86 while(find(e[j].x)==find(e[j].y))j++;87 ans+=(ll)e[j].w;88 fa[find(e[j].x)]=find(e[j].y);89 j++;90 }91 printf("%lld\n",ans);92 93 return 0;94 95 }
BZOJ3714: [PA2014]Kuglarz
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。