正文

保安站岗(代码片段)

stephen-f  stephen-f  2023-01-12  124

关键词：

分析：

树形dp刚刚入门，这是我做的第一个一个点同时受父亲节点和儿子节点控制的题目。

由于这个题中某一个点放不放保安与父亲和儿子都有关系（因为线段的两个端点嘛），所以我们做题时就要考虑全面。

假设dp数组为

~~有点啰嗦。。。~~

看了我的dp数组大家可能有疑问了，树形dp不是用儿子去更新父亲吗？dp不是没有后效性吗？为什么这个点可以看他的父亲？..其实我也是从别人嘴中知道有一种叫做未来计算的东西，就是可以把事先没有发生的但是肯定可以发生的费用加到答案中。

dp转移方程：

设

注意：

当然，自己不选也不一定所有的儿子都选，我们只需要选择一个最优的儿子，我们其实可以记录一个

if(f[v][0] <= f[v][1])
    f[x][1] += f[v][0];
    yes = true;

else 
    f[x][1] += f[v][1];
    minn = min(minn , f[v][0] - f[v][1]);

代码的话就是这样的。

$代码：$

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 2000;

inline int read()
    char ch = getchar();
    int f = 1 , x = 0;
    while(ch > ‘9‘ || ch < ‘0‘)if(ch == ‘-‘)f = -1;ch = getchar();
    while(ch >= ‘0‘ && ch <= ‘9‘)x = (x << 1) + (x << 3) + ch - ‘0‘;ch = getchar();
    return x * f;


int n,flag,k,m,r;
int f[maxn][10],son[maxn];
//f[i][0]:自己选 ，f[i][1]：自己不选，儿子选 ，f[i][2]：自己不选，父亲选 
int head[maxn],tot;

struct Edge
    int from,to,next;
edge[maxn << 1];

void add(int u,int v)
    edge[++tot].from = u;
    edge[tot].to = v;
    edge[tot].next = head[u];
    head[u] = tot;


void dfs(int x,int fa)
    f[x][0] = son[x];
    for(int i=head[x];i;i=edge[i].next)
        int v = edge[i].to;
        if(v != fa)  dfs(v , x);
    
    bool yes = false , have = false;
    int minn = 1e9 ; 
    for(int i=head[x];i;i=edge[i].next)
        int v = edge[i].to;
        have = true;
        f[x][0] += min(f[v][1] , min(f[v][2] , f[v][0]));
        f[x][2] += min(f[v][0] , f[v][1]);
        if(f[v][0] <= f[v][1])
            f[x][1] += f[v][0];
            yes = true;
        
        else 
            f[x][1] += f[v][1];
            minn = min(minn , f[v][0] - f[v][1]);
        
    
    if(!yes) f[x][1] += minn;
    if(!have) f[x][1] = 1e9;


int main()
    n = read();
    for(int i=1;i<=n;i++)
        flag = read(); k = read();
        m = read();
        son[flag] = k;
        if(m != 0)
            for(int j=1;j<=m;j++)
                r = read();
                add(flag , r);  add(r , flag);
            
        
    
    memset(f , 0 , sizeof(f));
    dfs(1 , 0);
    printf("%d
",min(f[1][1] , f[1][0]));
    return 0;

[luogu2458][sdoi2006]保安站岗(代码片段)

...免造成超市内的混乱和拥挤，准备临时从外单位调用部分保安来维持交通秩序。已知整个地下超市的所有通道呈一棵树的形状；某些通道之间可以互相望见。总经理要求所有通道的每个端点（树的顶点）都要有人全天候看守，在... 查看详情

[luogu2458][sdoi2006]保安站岗(代码片段)

[sdoi2006]保安站岗(代码片段)

题目链接第一遍不知道为什么就爆零了……第二遍改了一下策略，思路没变，结果不知道为什么就A了？？？树形DP经典问题：选择最少点以覆盖树上所有点（边）。对于本题，设dp[i][0/1][0/1]表示第i个节点，其父亲节点选/没选中... 查看详情

luogup2458[sdoi2006]保安站岗(代码片段)

...很久最后看讨论版才de出来bug要考虑三个状态1.父节点有保安2.本身有保安3.儿子节点放保安1.2.douhenhaokaolv3.不太容易，看了题解才有思路dp[u][2]：点u没有放置警察，且目前未被任何节点控制。所以u一定会被它的至少一个儿子控制... 查看详情

偷钻石（最小割2最大流）(代码片段)

目录问题分析一般场景模型转换构图代码问题m个保安监控n个钻石。钻石价值aia_iai，保安小费bib_ibi。小偷若向保安支付小费，则保安放松监控，小偷将偷得钻石。问：如何支付小费将获得最大收益。输入࿱... 查看详情

django之中间件7个保安(代码片段)

目录Django请求生命周期流程图什么是中间件？7个保安？自定义中间件中间件可以定义的五个方法？1.process_request(self,request)2.process_response3.process_view4.process_exception5.process_template_reponse中间件执行的流程Django请求生命周期流程图什... 查看详情

java并发系列终结篇：学校门口保安小王，这次彻底搞懂了java线程池的工作原理(代码片段)

前言多线程并发是Java语言中非常重要的一块内容，同时，也是Java基础的一个难点。说它重要是因为多线程是日常开发中频繁用到的知识，说它难是因为多线程并发涉及到的知识点非常之多，想要完全掌握Java的并... 查看详情

树形dp小结(代码片段)

...][0]+=dp[v][1];)(dp[u][1]+=min(dp[v][0],dp[v][1]);)3.最小支配集（SDOI保安站岗）(dp[i][0/1/2])表示这个点被自己覆盖，被儿子覆盖，被父亲覆盖(dp[u][0]+=min(dp[v][0],dp[v][1],dp[v][2]);)(dp[u][1]+=min(dp[v][1],dp[v][0]);)(注：如果u所有的儿子v的dp[v][1]<dp[v][... 查看详情

atcoderbeginnercontest207f-treepatrolling(树上背包)(代码片段)

...ta=0sta=0sta=0时,节点iii和他的直接儿子都没有放置保安当sta=1sta=1sta=1时,不管儿子怎样,反正点iii放置了保安当sta=2s 查看详情

es6中的proxy

...的。学习之后，在小编的简单理解，就和小区门口站岗的保安类似，满足条件才允许放行。在数据中，就是在获取值或者设置值的时候有个规则。大家还可以关注我的微信公众号，蜗牛全栈。一、es5处理代理语法letobj={}Object.defin... 查看详情

jxoi2018守卫(代码片段)

题目大概是给一些折线，问安排多少个保安才能监控全部折点。预处理出能否看到进行区间dp即可，转移用前缀和优化#include<cstdio>#include<algorithm>#include<iostream>usingnamespacestd;#definedbdoubleconstintINF=0x3f3f3f3f;constintmaxn=5010;... 查看详情

30分钟看懂catboost（python代码）

...的预测信贷用户是否会违约为例，假设city="北京市"且job="保安"的用户信用特别好，但不是北京市所有的用户都信用好，也不是所有的保安都信用特别好。只有北京市的保安这个群体查看详情

2023年全国最新保安员精选真题及答案44

百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等，提供在线做题刷题，在线模拟考试，助你考试轻松过关。441.单位自行招聘的保安员（）从事保安武... 查看详情

某pc企业保安对公司高层的灵魂拷问，太贪了！

查看详情

2023年全国最新保安员精选真题及答案31

百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等，提供在线做题刷题，在线模拟考试，助你考试轻松过关。311.某日，刘某到超市购物时，找到该超市... 查看详情

2023年全国最新保安员精选真题及答案38

百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等，提供在线做题刷题，在线模拟考试，助你考试轻松过关。381.对于保安员来说，秩序维护主要是指（&... 查看详情

聊一聊限流降级熔断(代码片段)

...词定义。限流限流场景我们经常遇到，有时候地铁里就被保安人员给我限流了，双十一抢购也被爸爸限流了。坐地铁之所以能限流是因为我们都要安检，有这个统一的地铁入口；浏览网查看详情

2023年全国最新保安员精选真题及答案47

百分百题库提供保安员考试试题、保安职业资格考试预测题、保安员考试真题、保安职业资格证考试题库等，提供在线做题刷题，在线模拟考试，助你考试轻松过关。471.机动车在消防栓或者消防队(站)门前（）... 查看详情