专栏首页数据结构与算法BZOJ 3714: [PA2014]Kuglarz(最小生成树)

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

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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • P2820 局域网

    题目背景 某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回...

    attack
  • 洛谷P4383 [八省联考2018]林克卡特树lct(DP凸优化/wqs二分)

    小L 最近沉迷于塞尔达传说:荒野之息(The Legend of Zelda: Breath of The Wild)无法自拔,他尤其喜欢游戏中的迷你挑战。

    attack
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • 【POJ 2886】Who Gets the Most Candies?

    约瑟夫问题的升级版,每次出去的是前一个出去的人位置+手上的数字(正往前,负往后)。第i个出去的人拿的糖是i的约数的个数。求拿糖最多的人和他的糖果数。

    饶文津
  • HDU4609 3-idiots(生成函数)

    但是如果直接算合法的方案的话会出现一点问题。我们在算的时候维护了一个后缀和表示乘起来大于等于这个数的方案。我们要求的方案需要满足i < j < k,但是这样计算...

    attack
  • codeforces 722C(带权并查集+反向思维)

    You are given an array consisting of n non-negative integers a 1, a 2, …, a n.

    dejavu1zz
  • 186. [USACO Oct08] 牧场旅行

    157. [USACO Nov07] 奶牛跨栏 186. [USACO Oct08] 牧场旅行 ★★   输入文件:pwalk.in   输出文件:pwalk....

    attack
  • P2820 局域网

    题目背景 某个局域网内有n(n<=100)台计算机,由于搭建局域网时工作人员的疏忽,现在局域网内的连接形成了回路,我们知道如果局域网形成回路那么数据将不停的在回...

    attack
  • 南京网络预选赛 The Preliminary Contest for ICPC Asia Nanjing 2019 H. Holy Grail 多源最短路

    用户2965768
  • P2746 [USACO5.3]校园网Network of Schools

    题目描述 一些学校连入一个电脑网络。那些学校已订立了协议:每个学校都会给其它的一些学校分发软件(称作“接受学校”)。注意即使 B 在 A 学校的分发列表中, A...

    attack

扫码关注云+社区

领取腾讯云代金券