[HEOI2015]兔子与樱花 树规+贪心
2024-10-10 00:10:02
鬼能想到是个贪心。明明觉得是树规啊。。又完美爆零。。
从叶子节点往上更新,能保证最优解(这块想了半天)。
证明:当你的子树上有能删的点而你不删时,可能会对子树的根节点有利,最好的情况是使子树根节点由不可删除变为可删除。但是,既然最终可能删一个点,还不如直接删现成能删的呢。。
用wei[]记录每个节点的权值(花数+儿子数),在更新结果时将权值更新即可。
#include #include #include #include #include #include using namespace std; #define pos(i,a,b) for(int i=(a);i<=(b);i++) #define N 2000500 int n,m; vector son[N]; int wei[N]; int ji[N]; int ans; bool tmp(const int &a,const int &b) { return wei[a] } void dp(int x) { if(ji[x]==0) return; pos(i,0,ji[x]-1) { dp(son[x][i]); } sort(son[x].begin(),son[x].end(),tmp); pos(i,0,ji[x]-1) { if(wei[x]-1+wei[son[x][i]]<=m) { ans++; wei[x]+=wei[son[x][i]]-1; } } } int main() { freopen("sakura.in","r",stdin); freopen("sakura.out","w",stdout); cin>>n>>m; pos(i,1,n) scanf("%d",&wei[i]); pos(i,1,n) { scanf("%d",&ji[i]); wei[i]+=ji[i]; pos(j,1,ji[i]) { int p; scanf("%d",&p); p++; son[i].push_back(p); } } dp(1); cout<<ans; //while(1); return 0; }
最新文章
- string和char*的相互转换
- 一个android样本的过保护
- IOS 杂笔- 6(KVC-KVO)
- eclipse字体的设置
- 离线安装Android开发环境的方法
- 车牌识别LPR(三)-- LPR系统整体结构
- php文件上传大小限制的修改方法大全
- VB execl文件后台代码,基础语法
- leetcode_question_85 Largest Rectangle in Histogram
- SQL求解两个时间差
- [luoguP2912] [USACO08OCT]牧场散步Pasture Walking(lca)
- 【USACO Mar08】 奶牛跑步 A-star k短路
- Linux连接虚拟机及操作指令
- 安装Redis 4.0单实例
- day60 pymysql
- MySQL表与表之间的关系详解
- 用面向对象计算BMI指数
- Go语言学习之3 流程控制、函数
- AIX查看CPU、内存等信息
- Ios8 Xcode6 设置Launch Image 启动图片