BZOJ 4557 JLOI2016 侦查守卫 树形dp
题目链接:https://www.lydsy.com/JudgeOnline/problem.php?id=4557
题意概述:
给出一棵树,每个点付出代价w[i]可以控制距离和它不超过d的点,现在给出一些点,问控制这些点的最小代价是多少。
分析:
观察一下数据范围发现算算法的复杂度可能和d有关。横看竖看这像是一个树形dp,所以我们就把d搞到状态方程里面去嘛怎么就完全没有想到呢......
既然要用树形dp,就要先分析一下性质。
一个点如果被选择成为控制点,那么它可以控制的点有:子树中深度不超过d的点,祖先中和它距离不超过d的点,以及祖先的子树中的一些点。
感觉很麻烦的样子......因为对于那些祖先子树中的点控制的方向突然向上又向下了。
我们考虑到常用的技巧,在树形dp中,如果两个点会对答案产生贡献,我们在其LCA处统计贡献。于是我们设两个dp方程:
f(i,x)表示i点的子树中需要被控制的点全部被控制,还可以向上控制x层的最小代价;g(i,x)表示i点的子树中x层及以下需要被控制的点全部被控制的最小代价。
需要向上控制x层,那么儿子中就需要有点可以向上控制x +1层的点被选择,对于新来的子树j有两种情况,一个是我们需要的点在这个新的子树中,一个是我们需要的点在原来的子树中。
f(i,x)=min(f(i,x)+g(j,x),f(j,x+1)+g(i,x+1))
init:一开始把每点i当成孤点,那么向上控制1~d层就只有靠自己,f值初始化为w[i];f[i][0],g[i][0]根据这个点本身是否需要监视来判断。
但是注意答案在控制的长度恰好为x的时候不一定是最优的,可能稍微控制的长度大一点答案反而更优,于是把方程的意义改一下,改成至少控制x层。
g(i,x)=sum{g(j,x-1)|i->j},g(i,0)=f(i,0)
小技巧:怎么维护至少这个性质?和看起来更劣的状态取min即可。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<algorithm>
#include<cmath>
#include<queue>
#include<set>
#include<map>
#include<vector>
#include<cctype>
#define inf 1e9
using namespace std;
const int maxn=;
const int maxd=; int N,D,M,W[maxn];
struct edge{ int to,next; }E[maxn<<];
int first[maxn],np,f[maxn][maxd],g[maxn][maxd];
bool ob[maxn]; void _scanf(int &x)
{
x=;
char ch=getchar();
while(ch<''||ch>'') ch=getchar();
while(ch>=''&&ch<='') x=x*+ch-'',ch=getchar();
}
void add_edge(int u,int v)
{
E[++np]=(edge){v,first[u]};
first[u]=np;
}
void data_in()
{
_scanf(N);_scanf(D);
for(int i=;i<=N;i++) _scanf(W[i]);
_scanf(M);
int x,y;
for(int i=;i<=M;i++){
_scanf(x); ob[x]=;
}
for(int i=;i<N;i++){
_scanf(x);_scanf(y);
add_edge(x,y); add_edge(y,x);
}
}
void DFS(int i,int fa)
{
for(int d=;d<=D;d++) f[i][d]=W[i];
f[i][D+]=inf;
if(ob[i]) f[i][]=g[i][]=W[i];
for(int p=first[i];p;p=E[p].next){
int j=E[p].to;
if(j==fa) continue;
DFS(j,i);
for(int d=;d<=D;d++)
f[i][d]=min(f[i][d]+g[j][d],f[j][d+]+g[i][d+]);
for(int d=D;d>=;d--) f[i][d]=min(f[i][d],f[i][d+]);
g[i][]=f[i][];
for(int d=;d<=D;d++) g[i][d]+=g[j][d-];
for(int d=;d<=D;d++) g[i][d]=min(g[i][d],g[i][d-]);
}
}
void work()
{
DFS(,);
printf("%d\n",f[][]);
}
int main()
{
data_in();
work();
return ;
}
最新文章
- Ice分布式程序设计—IceBox(Hello World Application)
- 弹窗插件 popup.js 完美修正版
- leetcode 74. Search a 2D Matrix
- ArcGIS Engine开发之旅07---文件地理数据库、个人地理数据库和 ArcSDE 地理数据库中的栅格存储加以比较 、打开栅格数据
- getch()函数
- FastDFS_v5.05安装配置
- qt学习笔记(五) QGraphicsPixmapItem与QGraphicsScene的编程实例 图标拖动渐变效果
- PYTHON线程知识再研习F---队列同步Queue
- js原生API----查找dom
- JavaScript作用域,内部函数比参数优先级高
- 安装memcache及php的memcached模块
- 入门嵌入式选择2440?树莓派?STM32?4412开发板?
- ORACLE用户表空间使用情况查询
- 聊聊JVM(二)说说GC的一些常见概念
- Debian stretch更换国内源
- English trip M1 - AC3 Teacher:Corrine
- linux环境中,ssh登录报错,Permission denied, please try again.
- 20145301赵嘉鑫 《网络对抗》Exp9 Web安全基础实践
- idea springboot应用启动
- Git很简单--图解攻略