over 2 years ago

其实就是课件搬运啦

都是一些小清新dp题,还挺有趣的


  • HAOI2015 T1

有一棵点数为N的树,树边有边权。

给你一个在0~N之内的正整数K,你要在这棵树中选择K个点,将其染成黑色,

并将其他的N-K个点染成白色 。

将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的收益。问收益最大值是多少。


设f[i][j]表示以i为根的子树中染黑了j个点对答案的最大贡献。
因为黑点白点总数一定,因此每条边的贡献就确定了,就可以直接转移了。
直接暴力转移的复杂度是, 其实就是枚举了这棵树上的每对点。


  • SRM 349 div1 hard

一个不透明袋子中有?个红球和?个蓝球,两个玩家交替操作,每次操作从袋子中取1,2,3个球(一个人只能确定取几个球,取出来的球具体是什么是随机的),而且每个人取出来的球是公开的,取走最后一个红球的人输。然而有 个邪恶的场外人员,趁管理人员不注意,提前取出了?个球(这?个球也是随机的)。

玩家只知道原来每种球的总数,以及被拿走了多少个球,并不知道 被拿走的是哪些球。 每个玩家都是人类智慧之神,求先手获胜的概率。

这题还是挺小清新的啊..


我最开始也是想到了这个错误的思路..
两个玩家是不知道取出的情况的..
后面这个转化十分自然..当然也不是十分好想。


  • [POI2016]Nim z utrudnieniem

这题还是不难想的..


  • [POI2015]Myjnie

有?家洗车店从左往右排成一排,每家店都有一个正整数价格?[?],有?个人要来消费,第?个人会驶过第a[?]个开始一直到第?[?]个洗车店,且会选择这些店中最便宜的一个进行一次消费。但是如果这个最便宜的价格大于 ?[?],那么这个人就不洗车了。

请给每家店指定一个价格,使得所有人花的钱的总和最大。

这题是个区间dp..似乎区间dp的题目不是那么好想..可能是NOIP之后区间dp的题目就少了。
首先把费用离散化。
f[i][j][k]表示[i,j]这段区间中最小价格为k的情况下的答案。转移就枚举是哪个位置选了k,然后左右分别记录前缀和来转移。


  • COCI2014/2015 Contest #1 ZABAVA

有?栋宿舍, ?个学生按顺序入住, 第?个学生入住第?[?]个宿舍, 每次入住的代 价为入住后该宿舍的人数, 有?次清空宿舍的机会, 即宿舍人数变成0, 求最小代价

很显然每个宿舍可以分开来做,最后一个DP合并起来。
假设第i个宿舍分配到了j次清空机会,那么平均分配显然是最优的(这个地方最开始没有想到,以为也要dp才行)


  • 最小通讯费用

给定一棵树,边权均为1。每个点上都可以建立通讯站,在第i个点上建立通讯站的费用是w[i]。对于没有建立通讯站的点,它的通讯费用是s[d],其中s是一个给定的数组,d为离它最近的通讯站与它的距离。求最小通讯费用。

dp[i][j]表示在离点i最近的通讯站距离为j的条件下,子树i中所有点的通讯费用总和的最小值。
dp[i][j]可以转移到dp[f[i]][j-1],dp[f[i]][j],dp[f[i]][j+1]
需要一维额外的状态来表示最近的通讯站是是否来自于子树内部

← 滚粗狗的自我修养之NEERC2014练习 GCJ2016 Qualification Round →
 
comments powered by Disqus