BZOJ 4027: [HEOI2015]兔子与樱花
2024-09-07 14:53:43
贪心
#include<cstdio>
#include<algorithm>
using namespace std;
int cnt,n,m,F[2000005],c[2000005],last[2000005],G[2000005],E[2000005];
struct node{
int to,next;
}e[2000005];
void add(int a,int b){
e[++cnt].to=b;
e[cnt].next=last[a];
last[a]=cnt;
}
void dfs(int x){
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
dfs(V);
}
int cnt=0;
F[x]=c[x];
for (int i=last[x]; i; i=e[i].next){
int V=e[i].to;
F[x]++;
E[++cnt]=F[V]-1;
G[x]+=G[V];
}
sort(E+1,E+cnt+1);
for (int i=1; i<=cnt; i++)
if (F[x]+E[i]<=m){
F[x]+=E[i];
G[x]++;
}
}
int main(){
scanf("%d%d",&n,&m);
for (int i=1; i<=n; i++) scanf("%d",&c[i]);
for (int i=0; i<n; i++){
int K;
scanf("%d",&K);
while (K--){
int x;
scanf("%d",&x);
add(i+1,x+1);
}
}
dfs(1);
printf("%d\n",G[1]);
return 0;
}
最新文章
- limux curl命令
- 4809 江哥的dp题c
- App.js – 用于移动 Web App 开发的 JS 界面库
- Jenkins进阶系列之——08Jenkins纳入版本控制
- ytu 1938:首字母变大写(水题)
- IOS开发之开篇--CocoaPods安装
- java小程序整理及排序算法
- Linux常用设置
- 提取数据表保存为XML文件
- VisualBox会造成VPN连接不上问题
- 关于cell中添加子视图 复用重叠问题的解决方法
- poj 1018 Communication System 枚举 VS 贪心
- 神经网络中的BP神经网络和贝叶斯
- NFV、DPDK以及部分用户态协议研究
- 【转】SHELL variables default value, ${var:-DEFAULT}和${var=DEFAULT}的一点区别
- [Swift]LeetCode388. 文件的最长绝对路径 | Longest Absolute File Path
- Ansible工具原理一
- CSS定位概述
- Docker入门5------生产力工具docker-compose
- docker启动失败(can&#39;t create unix socket /var/run/docker.sock: is a directory)
热门文章
- Spring Task ABC
- Java虚拟机内存分配与回收策略
- 时间日期相关:Date类、DateFormat类、Calendar类
- [转载]&mdash;Health Check Reports Problem: Dependency$ p_timestamp mismatch for VALID objects (文档 ID 781959.1)
- Windows Azure 配置Active Directory 主机(2)
- 重写strcpy函数,以实现strcpy的功能
- mysql数据库备份/恢复
- 如何对ABAP SE80 workbench做增强
- 在openSUSE 13.1上用gem安装rails无反应: gem install rails
- 【转】ios -- ViewController跳转+传值(方式一)