标签:动态规划

Educational Codeforces Round 39 Summary

huangkui 2018年3月7日 No Comments Problem, Summary , ,

Summary 这场比赛本来是一次上分的好机会,一开始做出来了四道题,Rank排在前300,结果B因为看错题并且PP太水而惨遭叉掉,Rank直接掉到1600+,又要掉分了 以后打CF一定一定一定一定一定一定一定一定在做完会做的题之后要检查之前的每一道题,每一回打CF都是想当然觉得应该没问题就没管了,导致惨遭FST

Luogu P1437 [HNOI2004]敲砖块(Dp)

huangkui 2018年1月15日 No Comments Problem ,

题目链接:传送门 Description 在一个凹槽中放置了 n 层砖块、最上面的一层有n 块砖,从上到下每层依次减少一块砖。每块砖 都有一个分值,敲掉这块砖就能得到相应的分值,如下图所示。 14 15 4 3 23 33 33 76 2 2 13 11 22 23 31 如果你想敲掉第 i 层的第j 块砖的话,若i=1,你可以直接敲掉它;若i>1,则你必须先敲掉第i-1 层的第j 和第j+1 块砖。 你现在可以敲掉最多 m 块砖,求得分最多能有 […]

洛谷P1273 有线电视网(树形背包)

huangkui 2017年8月19日 1 Comment Problem, 未分类 , , , ,

题目链接:传送门 Description 某收费有线电视网计划转播一场重要的足球比赛。他们的转播网和用户终端构成一棵树状结构,这棵树的根结点位于足球比赛的现场,树叶为各个用户终端,其他中转站为该树的内部节点。 从转播站到转播站以及从转播站到所有用户终端的信号传输费用都是已知的,一场转播的总费用等于传输信号的费用总和。 现在每个用户都准备了一笔费用想观看这场精彩的足球比赛,有线电视网有权决定给哪些用户提供信号而不给哪些用户提供信号。 写一个程序找出 […]

NOIP2016 换教室 期望DP

huangkui 2017年8月17日 No Comments Problem, 未分类 , , ,

题目链接:传送门 Description 有n个时间段,第i个时间段可以选择在ci教室上课,也可以选择申请换课,有ki概率申请通过,在di上课,另外1−ki的概率留在ci教室。 总共有v个教室,e条路径双向联通教室xi和yi,路径有权值wi。在课间时(相邻两个时间段的间隔中),你要从上一个教室走最短路径到下一个教室。 现在你有m次申请机会,只能提前申请一堆换课(也就是你不能在知道某一次申请结果后再去申请下一个换课)。求总距离的最小期望。 1≤n≤ […]

洛谷P2015 二叉苹果树(树形DP)

huangkui 2017年8月17日 No Comments Problem, 未分类 ,

题目链接:传送门 Description 有一棵苹果树,如果树枝有分叉,一定是分2叉(就是说没有只有1个儿子的结点) 这棵树共有N个结点(叶子点或者树枝分叉点),编号为1-N,树根编号一定是1。 我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有4个树枝的树 2 5 \ / 3 4 \ / 1 现在这颗树枝条太多了,需要剪枝。但是一些树枝上长有苹果。 给定需要保留的树枝数量,求出最多能留住多少苹果。

Page 1 of 2