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
输出一个整数,表示最少花费。
题解:
参考小胖的奇偶那道题。
那道题用的并查集维护。
如果知道 i..j 之间奇偶性的话,实际上知道的是 sum[j]-sum[i-1]的奇偶性(sum为前缀和)。
可以用扩展域的并查集维护任意两个sum[i]之间的差值。
有了这个结论,如果全部知道哪些杯底有球,就需要所有的sum之间的关系已知,也就是并查集中所有点都在一个集合中,是一棵树。
所以遍转化成了最小生成树问题。
代码:
Kruskal 10384 ms
#include<cstdio> #include<cstring> #include<algorithm> //by zrt //problem: using namespace std; int n; struct N{ int x,y,w; }map[*]; int tot; bool cmp(N a,N b){ return a.w<b.w; } ]; int get(int x){ return f[x]==x?x:f[x]=get(f[x]); } int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d",&n); ;i<=n;i++){ for(int j=i;j<=n;j++){ scanf("%d",&map[tot].w); map[tot].x=i; map[tot].y=j+; tot++; } } sort(map,map+tot,cmp); ); ;i<=n+;i++) f[i]=i; ;i<tot;i++){ if(get(map[i].x)!=get(map[i].y)){ f[get(map[i].x)]=get(map[i].y); cost+=map[i].w; } } printf("%lld\n",cost); ; }
Prim 16480 ms
#include<cstdio> #include<cstring> #include<algorithm> #include<queue> //by zrt //problem: using namespace std; int n; ][]; struct N{ int x,w; N(,){ x=a,w=b; } friend bool operator < (N a,N b){ return a.w>b.w; } }; priority_queue<N> q; ]; int main(){ #ifdef LOCAL freopen("in.txt","r",stdin); freopen("out.txt","w",stdout); #endif scanf("%d",&n); int x; ;i<=n;i++){ for(int j=i;j<=n;j++){ scanf("%d",&x); val[j+][i]=val[i][j+]=x; } } ); q.push(N(,)); int c; n=n+; while(!q.empty()){ x=q.top().x;c=q.top().w;q.pop(); if(vis[x]) continue; vis[x]=;cost+=c; ;i<=n;i++){ if(!vis[i]){ q.push(N(i,val[x][i])); } } } printf("%lld\n",cost); ; }