夢に僕らで帆を張って
来るべき日のために夜を超え

标签 DP 下的文章

November 11, 2019

洛谷P3177/HAOI2015 树上染色

题意有一棵点数为$N$的树,树边有边权。给你一个在$0 \sim N$之内的正整数$K$,你要在这棵树中选择$K$个点,将其染成黑色,并将其他 的$N-K$个点染成白色将所有点染色后,你会获得黑点两两之间的距离加上白点两两之间的距离的和的受益。问受益最大值是多少数据范围:$0 \le k \le n \le 2000$题解因为计算答案时需要对整颗树考虑,而一条边的贡献为$$一侧的黑/白色点数...
November 11, 2019

洛谷P1270 “访问”美术馆

题意经过数月的精心准备,Peer Brelstet,一个出了名的盗画者,准备开始他的下一个行动。艺术馆的结构,每条走廊要么分叉为两条走廊,要么通向一个展览室。Peer知道每个展室里藏画的数量,并且他精确测量了通过每条走廊的时间。由于经验老到,他拿下一幅画需要5秒的时间。你的任务是编一个程序,计算在警察赶来之前,他最多能偷到多少幅画题解树上背包注意读入代码:#include<iostre...
November 11, 2019

洛谷P2014 选课

题意现在有N门功课,每门课有个学分,每门课有一门或没有直接先修课(若课程$a$是课程$b$的先修课即只有学完了课程$a$,才能学习课程$b$)。一个学生要从这些课程里选择$M$门课程学习,问他能获得的最大学分是多少?数据范围:$1 \le n,m \le 300$题解树上背包用$dp[u][i]$表示以$u$为根的子树中选择$j$门课的最大学分代码:#include<iostream&...
November 11, 2019

洛谷P1122 最大子树和

题意求树上联通块的最大权值和数据范围:$n \le 16000$题解树形$\text{dp}$用$dp[u]$表示以$u$为根的子树中的最大权值和代码:#include<iostream> #include<cstdio> #include<algorithm> #include<cstring> using namespace std; co...
November 4, 2019

洛谷P1450/HAOI2008 硬币购物

题意硬币购物一共有$4$种硬币。面值分别为$c_1,c_2,c_3,c_4$某人去商店买东西,去了$t$次。每次带$d_i$枚$c_i$硬币,买$s$的价值的东西,请问每次有多少种付款方法数据范围:$d_i,s \le 100000$题解显然不能直接多重背包,会TLE若不考虑限制条件,先当作完全背包处理,再在每次询问的时候将超出部分的情况减去需要减去的部分也是一个完全背包,容量为$s-c_i...
November 3, 2019

洛谷P3183/HAOI2016 食物链

题意给出$n$个物种和$m$条关系,求食物链条数数据范围:$1 \le n \le 100000,0 \le m \le 200000$题解记忆化搜索食物链从入度为$0$的点开始,到出度为$0$的点结束注意单独的一种孤立生物不算一条食物链代码:#include<iostream> #include<cstdio> using namespace std; const ...
November 2, 2019

洛谷P4158/SCOI2009 粉刷匠

题意windy有$n$条木板需要被粉刷,每条木板被分为$m$个格子,每个格子要被刷成红色或蓝色windy每次粉刷,只能选择一条木板上一段连续的格子,然后涂上一种颜色 每个格子最多只能被粉刷一次如果windy只能粉刷$t$次,他最多能正确粉刷多少格子?一个格子如果未被粉刷或者被粉刷错颜色,就算错误粉刷数据范围:$1 \le n,m \le 50,1 \le t \le 2500$题解$\tex...
November 2, 2019

洛谷P2466/SDOI2008 Sue的小球

题意略数据范围:$n \le 1000$题解区间$\text{dp}$容易证明,在完成一个区间后处于左/右端点最优由于输入无序,首先按$x$排序,并统计$v$的前缀和以优化计算;另外起始点不一定有球,因此加入起始点用$f[l][r][0/1]$表示已接到区间$[l,r]$的球,现在处于$0$(左端点)/$1$(右端点)失去的最小价值那么区间$[l,r]$由$[l+1,r]$或$[l,r-1]...