采药(medic) 【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,…
分类:OIer之路
背包型DP【仅题目】
背包模型 采药(medic) 【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药…
能量项链(区间型DP)解题日志
能量项链(energy) 【问题描述】 在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有n颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的…
石子归并(区间型dp) 代码日志
石子归并(merge) 【问题描述】 在一个操场按次序从左到右摆放着n堆石子(n≤100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分,求最小的得分总…
区间型DP【仅题目】
石子归并(merge) 【问题描述】 在一个操场按次序从左到右摆放着n堆石子(n≤100),现要将石子有次序地合并成一堆。规定每次只能选取相邻的两堆合并成新的一堆,并将新的一堆的石子数,记为该次合并的得分,求最小的得分总…
又上锁妖塔(动态规划练习) 解题日志
又上锁妖塔 (tower.in/tower.out) [题目描述] 小D在X星买完了想要的东西,在飞往下一个目的地的途中,正无聊的他转头看了看身边的小A,发现小A正在玩<仙剑>,可是小A很奇怪,他一直在锁妖塔的周围…
维修栅栏(动态规划练习) 解题日志
维修栅栏 输入文件:fence.in 输出文件:fence.out 问题描述: 小z最近当上了农场主!不过,还没有来得及庆祝,一件棘手的问题就摆在了小z的面前。农场的栅栏,由于年久失修,出现了多处破损。栅栏是由n块木板组…
三角蛋糕(坐标规划类DP) 解题日志
三角蛋糕(trigon) XP在机房里放了一块正三角形的大蛋糕,但是第二天他发现蛋糕被老鼠咬坏了。 XP不想让蛋糕白白的被浪费,于是他把蛋糕分割成了一个个的小正三角形(如上图所示)。黑色的小正三角形表示老鼠把那一块咬坏了…
传纸条(坐标规划型DP) 解题日志
传纸条 (message) 【问题描述】 小渊和小轩是好朋友也是同班同学,他们在一起总有谈不完的话题。一次素质拓展活动中,班上同学安排做成一个m行n列的矩阵,而小渊和小轩被安排在矩阵对角线的两端,因此,他们就无法直接交谈…
EXCHANGE(动态规划练习) 解题日志
EXCHANGE(exchange) 问题描述: Dave偶然获得了未来几天的美元(dollars)与马克(marks)之间的兑换率。例如Dave开始有100marks,请编写个程序帮助Dave找出最好的买卖mark…