BZOJ 3714: [PA2014]Kuglarz(最小生成树)

2018-02-27 08:59:40来源:cnblogs.com作者:自为风月马前卒人点击

分享
Time Limit: 20 Sec  Memory Limit: 128 MB
Submit: 1134  Solved: 599
[Submit][Status][Discuss]

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

HINT

 

Source

鸣谢Jcvb

离正解一步之遥QWQ..

我们把此题的模型转换一下

令$sum[i]$表示$0-i$的前缀和

这样的话我们假设要知道$i-j$的奇偶性实际就是知道$sum[j]-sum[i-1]$的奇偶性

因此我们如果想要求$sum[j]-sum[i-1]$的奇偶性,就在$i-1$到$j$之间连一条边,为询问的权值

最终要求整个图联通

因此跑一边最小生成树就好了

当然你如果和我一样比较弱的话,经过观察归纳不难发现

当我们知道了$1-2$,那我们只要再知道$1-1$或者$2-2$就可以,

此时我们如果需要知道$1-3$那么我们只需要知道$3-3$

继续推下去,然后多举几个例子就会发现:最优的询问区间应该是互不重叠的

这样就是个最小生成树!

然后代码写挂了GG....

#include<cstdio>#include<algorithm>#define int long long const int MAXN=3*1e6+10;using namespace std;inline int read(){    char c=getchar();int x=0,f=1;    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}    while(c>='0'&&c<='9'){x=x*10+c-'0';c=getchar();}    return x*f;}int N;struct node{    int u,v,w;}edge[MAXN];int num=1;void AddEdge(int x,int y,int z){    edge[num].u=x;    edge[num].v=y;    edge[num++].w=z;}int comp(const node &a,const node &b){return a.w<b.w;}int fa[MAXN];int find(int x){    if(fa[x]==x) return fa[x];    else return fa[x]=find(fa[x]);}void unionn(int x,int y){    int fx=find(x);    int fy=find(y);    fa[fx]=fy;}void Kruskal(){    sort(edge+1,edge+num,comp);        int tot=0,sum=0;    for(int i=1;i<=num-1;i++)    {        if(find(edge[i].u)!=find(edge[i].v))        {            unionn(edge[i].u,edge[i].v);            sum+=edge[i].w;            tot++;            if(tot==N) break;        }    }    printf("%lld",sum);}main(){    #ifdef WIN32    freopen("a.in","r",stdin);    #else    #endif    N=read();    for(int i=1;i<=N;i++) fa[i]=i;    for(int i=1;i<=N;i++)    {        for(int j=i;j<=N;j++)        {            int x=read();            AddEdge(i-1,j,x);        }    }    Kruskal();    return 0;}

最新文章

123

最新摄影

闪念基因

微信扫一扫

第七城市微信公众平台