A simple Blog for wyx I've been down the bottle hoping.
POJ 1947 Rebuilding Roads 树形dp
发表于: | 分类:Oi | 评论:0 | 阅读:45
这题还是挺经典的 简单说一下思路和一些需要注意的细节 用$f(i,j)$表示在以$i$为根的子树中选择$k$个连续的点的最小花费 $f(i,j) = min(f(i,k)+f(son,j-k))$ 需要注意的是统计答案的时候 除了根节点,剩下的都得+1统计,因为需...

阅读全文>>

BZOJ 3727 树形$dp$ 数学
发表于: | 分类:Oi | 评论:0 | 阅读:44
$description$ 吉丽YY了一道神题,题面是这样的: “一棵n个点的树,每条边长度为1,第i个结点居住着a[i]个人。假设在i结点举行会议,所有人都从原住址沿着最短路径来到i结点,行走的总路程为b[i]。输出所有b[i]。” 吉丽已经造好了数据,但熊孩...

阅读全文>>

BZOJ 4272 挂件
发表于: | 分类:Oi | 评论:0 | 阅读:52
这题还是挺简单的 $dp$ $f(i,j)$表示到达第$i$个物品还剩$j$个挂钩空余的最多愉悦度 $f(i,j) = max(f(i,j),f(i-1,j))$即该物品不选 $f(i,j-a[i].lmt+1) = max(f(i-1,j)+a[i].val,f...

阅读全文>>

BZOJ 2151 种树 贪心 双向链表优化
发表于: | 分类:Oi | 评论:0 | 阅读:40
给你一个$n$个点的环,每个点有点权,在环上取出互不相邻的$m$个点,求最大值 我们可以贪心,将所有的点扔入一个堆里 每次取出堆顶的元素,然后在双向链表中删去这个点 然而这样可能是错的,比如$1 \quad 3 \quad 5 \quad 4$ 正确答案应该是7 ...

阅读全文>>

BZOJ 2086 poi2010 Blocks 树状数组
发表于: | 分类:Oi | 评论:0 | 阅读:53
$description$ 共有m部电影,编号为1~m,第i部电影的好看值为w[i]。 在n天之中(从1~n编号)每天会放映一部电影,第i天放映的是第f[i]部。 你可以选择l,r(1<=l<=r<=n),并观看第l,l+1,…,r天内所有的电影...

阅读全文>>

Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP