树形DP+RMQ+单调队列(Bob’s Race HDU4123)

摘要:
分析:给出一个树形图。首先,使用dp计算每个点可以通过的最远距离,然后使用rmq计算间隔的最大值,最后,使用单调队列查询结果的复杂性#include“studio.h”#incluse“string.h”#includes“stdlib.h”#1included“queue”#incloude“algorithm”#include”string“#incluce“math.h”#includ“vector”#induce“stack”#in包括“map”#defineps1e-4#definein10000000#defineM50009#definePiac osusingnamespacestd;结构节点{intu,v,w,next;}边缘[M*2];intt,head[M],归属[M]、dis[M][4]、Log[M];intdp_最大值[M][17],dp_最小值[M][17];//请注意二维数组的大小。如果它太大,超时void init(){t=0;memset;}将出现voidadd{//edge[t].u=u;edge[t].v=v;edge[1t].w=w;edge[t]。next=head[u];head[u]=t++;}voidfs{dis[u][0]=dis[u][1]=dis[u][2]=0;对于(inti=头[u];i!

题意:有n个房子,这些房子被n-1条道路连接,有一些运动员从一个房子为起点尽可能跑最远的距离且不能通过一条道路超过两次,这些运行员不能选择同样的起点,这些运动员跑的最远距离和最近距离的差值不能超过Q,这些运行员的起点房间编号都是连续的,问最多可以选择多少个运动员跑步?

分析:就是给出一颗树形图,先用dp求出每个点所能经过的最远距离,然后用rmq求区间最值,最后用单调队列询问结果(n)的复杂度

#include"stdio.h"
#include"string.h"
#include"stdlib.h"
#include"queue"
#include"algorithm"
#include"string.h"
#include"string"
#include"math.h"
#include"vector"
#include"stack"
#include"map"
#define eps 1e-4
#define inf 10000000
#define M 50009
#define PI acos(-1.0)
using namespace std;
struct node
{
    int u,v,w,next;
}edge[M*2];
int t,head[M],belong[M],dis[M][4],Log[M];
int dp_max[M][17],dp_min[M][17];//注意第二维的数组大小,太大会超时
void init()
{
    t=0;
    memset(head,-1,sizeof(head));
}
void add(int u,int v,int w)
{
    //edge[t].u=u;
    edge[t].v=v;
    edge[t].w=w;
    edge[t].next=head[u];
    head[u]=t++;
}
void dfs(int u,int f)
{
    dis[u][0]=dis[u][1]=dis[u][2]=0;
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)continue;
        dfs(v,u);
        if(dis[u][0]<dis[v][0]+edge[i].w)
        {
            dis[u][1]=dis[u][0];
            dis[u][0]=dis[v][0]+edge[i].w;
            belong[u]=v;
        }
        else if(dis[u][1]<dis[v][0]+edge[i].w)
            dis[u][1]=dis[v][0]+edge[i].w;
    }
}
void dfs1(int u,int f)
{
    for(int i=head[u];i!=-1;i=edge[i].next)
    {
        int v=edge[i].v;
        if(v==f)continue;
        if(v==belong[u])
            dis[v][2]=max(dis[u][1],dis[u][2])+edge[i].w;
        else
            dis[v][2]=max(dis[u][0],dis[u][2])+edge[i].w;
        dfs1(v,u);
    }
}
void RMQ(int n)
{
    int i,j;
    int m=Log[n];
    for(i=1;i<=n;i++)
        dp_min[i][0]=dp_max[i][0]=dis[i][3];
    for(j=1;j<=m;j++)
    {
        for(i=1;i<=n+1-(1<<j);i++)
        {
            dp_max[i][j]=max(dp_max[i][j-1],dp_max[i+(1<<(j-1))][j-1]);
            dp_min[i][j]=min(dp_min[i][j-1],dp_min[i+(1<<(j-1))][j-1]);
        }
    }
}
int lcp(int x,int y)
{
    int m=Log[y-x+1];
    return max(dp_max[x][m],dp_max[y+1-(1<<m)][m])-min(dp_min[x][m],dp_min[y+1-(1<<m)][m]);
}
int main()
{
    int n,m,i,a,b,c;
    Log[0] = -1;
    for(int i = 1;i <M;i++)
        Log[i] = ((i&(i-1)) == 0)?Log[i-1]+1:Log[i-1];
    while(scanf("%d%d",&n,&m),m||n)
    {
        init();
        for(i=1;i<n;i++)
        {
            scanf("%d%d%d",&a,&b,&c);
            add(a,b,c);
            add(b,a,c);
        }
        dfs(1,-1);
        dfs1(1,-1);
        for(i=1;i<=n;i++)
        {
            dis[i][3]=max(dis[i][0],dis[i][2]);
            //printf("%d
",dis[i][3]);
        }
        RMQ(n);
        for(i=1;i<=m;i++)
        {
            int Q;
            scanf("%d",&Q);
            int l,r;
            l=r=1;
            int ans=0;
            while(r<=n)
            {
                int cha=lcp(l,r);
                if(cha<=Q)
                {
                    ans=max(ans,r-l+1);
                    r++;
                }
                else
                    l++;
            }
            printf("%d
",ans);
        }
    }
    return 0;
}

免责声明:文章转载自《树形DP+RMQ+单调队列(Bob’s Race HDU4123)》仅用于学习参考。如对内容有疑问,请及时联系本站处理。

上篇flask中内置的sessioniptables关键学习总结下篇

宿迁高防,2C2G15M,22元/月;香港BGP,2C5G5M,25元/月 雨云优惠码:MjYwNzM=

相关文章

Qt-数据库操作SQLite

1  简介 参考视频:https://www.bilibili.com/video/BV1XW411x7NU?p=88 说明:本文对在Qt中操作SQLite做简要说明。 SQLite:SQLite 是一个软件库,实现了自给自足的、无服务器的、零配置的、事务性的 SQL 数据库引擎。具体的操作命令可参考:https://www.runoob.com/sqli...

Android源码分析(一)-----如何快速掌握Android编译文件

一 : Android.mk文件概述 主要向编译系统指定相应的编译规则。会被解析一次或多次。因此尽量减少源码中声明变量,因为这些变量可能会被多次定义从而影响到后面的解析。这个文件的语法会把源代码组织成模块,每个模块属于下列类型之一: - APK程序:一般的Android程序,编译打包生成apk文件。 - JAVA库:java类库,编译打包生成jar包文件。...

操作笔记:linux下安装mysql

1,检查linux下是否安装了mysql shell指令如下: [root@iZ945sgm0ugZ ~]# rpm -qa|grep -i mysql 如果有的话:做出挨个删除(eg:rpm -ev mysql-connector-odbc-5.2.5-6.el7.x86_64) [root@iZ945sgm0ugZ ~]# rpm -qa|grep -...

kernel 目录 解析

核心源码的顶层是/usr/src/linux目录,在此目录下你可以看到大量子目录: arch 这个子目录包含了所有体系结构相关的核心代码。它还包含每种支持的体系结构的子目录,如i386。 include  这个目录包括了用来重构核心的大多数include文件。对于每种支持的体系结构分别有一个子目录。此目录中的asm子目录中是对应某种处理器的符号连接,如i...

c++中的.hpp文件

http://blog.chinaunix.net/uid-24118190-id-75239.html hpp,其实质就是将.cpp的实现代码混入.h头文件当中,定义与实现都包含在同一文件,则该类的调用者只需要include该hpp文件即可,无需再将cpp加入到project中进行编译。 而实现代码将直接编译到调用者的obj文件中,不再生成单独的obj,...

Qt 访问网络

一、前言 Qt 中访问网络使用 QNetworkAccessManager,它的 API 是异步的,这样在访问网络的时候不需要启动一个线程,在线程里执行请求的代码。(但这一点在有时候需要阻塞时就是个麻烦了) 需要注意一点的是,请求响应的对象 QNetworkReply 需要我们自己手动的删除,一般都会在 QNetworkAccessManager::fin...