博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
BZOJ4557:[JLOI2016/SHOI2016]侦察守卫——题解
阅读量:5855 次
发布时间:2019-06-19

本文共 2245 字,大约阅读时间需要 7 分钟。

小R和B神正在玩一款游戏。这款游戏的地图由N个点和N-1条无向边组成,每条无向边连接两个点,且地图是连通的。换句话说,游戏的地图是一棵有N个节点的树。

游戏中有一种道具叫做侦查守卫,当一名玩家在一个点上放置侦查守卫后,它可以监视这个点以及与这个点的距离在D以内的所有点。这里两个点之间的距离定义为它们在树上的距离,也就是两个点之间唯一的简单路径上所经过边的条数。在一个点上放置侦查守卫需要付出一定的代价,在不同点放置守卫的代价可能不同。

现在小R知道了所有B神可能会出现的位置,请你计算监视所有这些位置的最小代价。

dp状态很好想,但是这个式子我菜我是真的推不出来,其他的巨佬切题的速度叹为观止,只能感叹我的智商摆在这里。

参考:

一眼是个树形dp,二眼$d$很小,可以直接做成一维状态,那么直接设$f[i][j]$为$i$子树从$i$往下$j$层都没有覆盖的代价,$g[i][j]$为$i$的子树全覆盖,往上还可以覆盖$j$层的代价。二者正好是互补的。

(PS:层数也包括i本身,换句话说,$j=0$时$i$并没有被覆盖,我在这里纠结了很久。)

(PPS:既然$g[i][j]$都可以覆盖上$j$层,那它也能覆盖下$j$层。)

之后对于dp式子慢慢剖析因为我自己都云里雾里的

边界就是当点$u$为关键点时$f[u][0]=g[u][0]=w[u]$这个点一定是要放一个的,如果不是的话显然我们就不需要放了,初值为0。

 

初始化就不说了。

对于每个儿子结点v,我们有:

$g[u][j]=min(g[u][j]+f[v][j],g[v][j+1]+f[u][j+1])$(所以明白f和g是互补的才能看懂)

当然也有可能出现这种的:$g[u][j]=min(g[u][j],g[u][j+1])$

推完g来推f,首先$f[u][0]=g[u][0]$因为此时二者状态等价。

然后显然的,$f[u][j]+=f[v][j-1]$

以及也有可能出现这种的:$f[u][j]=min(f[u][j],f[u][j-1])$

(所以其实核心还是在状态含义上而非式子,含义搞懂式子就很显然了。)

#include#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;typedef long long ll;const int N=5e5+5;const int D=21;const int INF=1e9;inline int read(){ int X=0,w=0;char ch=0; while(!isdigit(ch)){w|=ch=='-';ch=getchar();} while(isdigit(ch))X=(X<<3)+(X<<1)+(ch^48),ch=getchar(); return w?-X:X;}struct node{ int to,nxt;}e[N*2];int n,d,m,cnt,head[N],w[N];int f[N][D],g[N][D];bool im[N];inline void add(int u,int v){ e[++cnt].to=v;e[cnt].nxt=head[u];head[u]=cnt;}void dfs(int u,int fa){ if(im[u])f[u][0]=g[u][0]=w[u]; for(int i=1;i<=d;i++)g[u][i]=w[u]; g[u][d+1]=INF; for(int i=head[u];i;i=e[i].nxt){ int v=e[i].to; if(v==fa)continue; dfs(v,u); for(int j=d;j>=0;j--)g[u][j]=min(g[u][j]+f[v][j],g[v][j+1]+f[u][j+1]); for(int j=d;j>=0;j--)g[u][j]=min(g[u][j],g[u][j+1]); f[u][0]=g[u][0]; for(int j=1;j<=d+1;j++)f[u][j]+=f[v][j-1]; for(int j=1;j<=d+1;j++)f[u][j]=min(f[u][j],f[u][j-1]); }}int main(){ n=read(),d=read(); for(int i=1;i<=n;i++)w[i]=read(); m=read(); for(int i=1;i<=m;i++)im[read()]=1; for(int i=1;i

+++++++++++++++++++++++++++++++++++++++++++

+本文作者:luyouqi233。               +

+欢迎访问我的博客:+

+++++++++++++++++++++++++++++++++++++++++++

转载于:https://www.cnblogs.com/luyouqi233/p/9193761.html

你可能感兴趣的文章
webview屏蔽加载某段html,分段中的WebView不加载HTML字符串
查看>>
html自定义datajs,HTML5的自定义属性data-*详细介绍和JS操作实例
查看>>
『摄影欣赏』15幅迷人的来自世界各地的婴儿照片【组图】
查看>>
Jquery-Ajax常用总结
查看>>
每日英语:U.S. Media Firms Stymied in China
查看>>
sql转Linq的工具
查看>>
17、屏幕适配,多语言支持,手机类型适配
查看>>
第37周二
查看>>
模拟地与数字地(转)
查看>>
uGUI练习(八) InputField
查看>>
windows Server 2008 R2 IE增强安全配置正在阻止来自下列网站的内容
查看>>
怎样配置nginx同一时候执行不同版本号的php-fpm
查看>>
js控制图片缩放、水平和垂直方向居中对齐
查看>>
linux signal 处理
查看>>
Codeforces Round #234 (Div. 2) B. Inna and New Matrix of Candies
查看>>
ByteBuffer的allocate和allocateDirect
查看>>
关于sources.list和apt-get [转载]
查看>>
《大型站点技术架构》1:概述
查看>>
SNMP协议具体解释
查看>>
Eclipse代码自动提示
查看>>