$Loj10157$ 皇宫看守 树形$DP$

时间：2023-03-09 19:07:25
$Loj10157$ 皇宫看守 树形$DP$

loj

Description

有一些宫殿,它们呈树形结构,相邻的宫殿之间可以互相望见.在一些宫殿设立士兵,使得所有的宫殿都有士兵或是被士兵望见.求最小士兵数.

Sol

状态：

f[x][0] 表示结点i被父结点覆盖,以i为根的树需要的最小士兵数

f[x][1] 表示结点i被自己覆盖,以i为根的树需要的最小士兵数

f[x][2] 表示结点i被子结点覆盖,以i为根的树需要的最小士兵数

转移：(y是x的子结点)

f[x][0]=Σmin(f[y][1],f[y][2])

f[x][1]=Σmin(f[y][1],f[y][2],f[y][3])

f[x][2]=Σmin(f[y][1],f[y][2])+d,d=min(f[y][1]-min(f[y][1],f[y][2]))

就f[x][2]的转移稍微难想一点点,可以这样理解:

先算f[x][2]=Σmin(f[y][1],f[y][2]),但是这样并不能保证一定在某个y上设立了士兵

如果要保证这一点,那么就可能产生附加的代价,就是f[y][1]-min(f[y][1],f[y][2]),加上最小代价即可

Code

 #include<iostream>

 #include<cstdio>

 #include<vector>

 #define Rg register

 #define il inline

 #define inf 2100000000

 #define go(i,a,b) for(Rg int i=a;i<=b;++i)

 using namespace std;

 il int read()

 {

     int x=,y=;char c=getchar();

     while(c<''||c>''){if(c=='-')y=-;c=getchar();}

     while(c>=''&&c<=''){x=(x<<)+(x<<)+c-'';c=getchar();}

     return x*y;

 }

 const int N=;

 int n,rt,f[N][],a[N];

 vector<int> c[N];

 bool d[N];

 il void dp(int x)

 {

     f[x][]=a[x];

     int hhh=c[x].size()-,t=inf;

     if(hhh<)return;

     f[x][]=;

     go(i,,hhh)

     {

         int y=c[x][i];dp(y);

         f[x][]+=min(f[y][],f[y][]);

         f[x][]+=min(f[y][],min(f[y][],f[y][]));

         t=min(t,f[y][]-min(f[y][],f[y][]));

     }

     f[x][]=f[x][]+t;

 }

 int main()

 {

     n=read();

     go(i,,n)

     {

         int t=read(),m,x;

         a[t]=read();m=read();

         while(m--){x=read();c[t].push_back(x);d[x]=;}

     }

     go(i,,n)f[i][]=inf;

     go(i,,n)if(!d[i]){rt=i;break;}

     dp(rt);

     printf("%d\n",min(f[rt][],f[rt][]));

     return ;

 }

随机推荐

  1. Mysql 数据库优化(一)

    一 避免网页访问错误 1  数据库连接timeout产生页面5xx错误 2 慢查询造成页面无法加载 3 阻塞造成数据无法提交 二 增加数据库的稳定性 三 优化用户体验 1 流畅的页面访问速度 2 良好 ...

  2. docker oracle install

    https://hub.docker.com/r/9fevrier/oracle-11g Informations Oracle directory : /opt/oracle Data direct ...

  3. oracle中的闪回

    项目中运用: 首先说明:闪回方法有一个前提,就是需要尽早的发现问题,果断的采取行动.若误操作的记录已经在UNDO表空间中被清除,则此方法就不可行了,需要另寻他法. 例如: SELECT * FROM ...

  4. UI2CODE智能生成代码——组件识别篇

    1.背景 在<UI2CODE——整体设计篇>中,我们介绍了UI2CODE工程的整体流程: 在组件识别这个环节,需要有一种处理布局信息的方法,来解析和计算控件间的布局关系(比如识别业务组件( ...

  5. 杭电多校第二场1012 L - Longest Subarray ce 线段树

    这题是真的秀...我服了...线段树用好了,感觉什么都可以写... 题目大意:给你一个串,问满足以下条件的子串中最长的是多长:对于每个数字,要么在这个子串没出现过,要么出现次数超过k次. 我们对于每一 ...

  6. [C#] 汉字转拼音，支持多音字

    这份代码大概不是严格意义上正确的,但是一般场景用用应该没问题. using System; using System.Collections.Generic; using System.Linq; u ...

  7. HTML--CSS样式表--基本概念（超链接的状态）

    样式表的基本概念 一.样式表的分类 1.内联样式表 和HTML联合显示,控制精确,但是可重用性差,冗余较多. 例:<p style="font-size:14px;"> ...

  8. Python--day20--模块的导入

    1,模块的导入步骤: 2,,给文件起别名的用处: 重命名之后,原来的名字就不能用了 3,虽然这样写可以,但是不推荐,代码可读性不强,以后代码的修改成本也增加: 4,模块的导入顺序: 5,导入变量名的两 ...

  9. 2017年NOIP普及组复赛题解

    题目涉及算法: 成绩:入门题: 图书管理员:模拟: 棋盘:最短路/广搜: 跳房子:RMQ/二分答案/DP(本人解法). 成绩 题目链接:https://www.luogu.org/problemnew ...

  10. java Jre和Jdk的区别?

    JRE:(Java Runtime Environment),java运行环境.包括Java虚拟机(JVM Java Virtual Machine)和Java程序所需的核心类库等,如果想要运行一个开 ...

相关文章