求最长公共子序列(lcs) 【问题描述】 字符序列的子序列是指从给定字符序列中随意地(不一定连续)去掉若干个字符(可能一个也不去掉)后所形成的字符序列。令给定的字符序列X=“x0,x1,…,xm-1”,序列Y=“y0,y…
防卫导弹(序列型DP) 解题日志
防卫导弹(dao) 【问题描述】 一种新型的防卫导弹可截击多个攻击导弹.它可以向前飞行,也可以用很快的速度向下飞行,可以毫无损伤地截击进攻导弹,但不可以向后或向上飞行.但有一个缺点,尽管它发射时可以达到任意高度,但它只能…
最大连续子序列(序列型DP) 解题日志
最大连续子序列(subsequence) 【问题描述】 给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, ..., Nj },其中 1 <= i <= …
序列型DP【仅题目】
常见的动态规划模型——序列模型 一、最大连续子序列和 最大连续子序列(subsequence) 【问题描述】 给定K个整数的序列{ N1, N2, ..., NK },其任意连续子序列可表示为{ Ni, Ni+1, …
逃亡的准备(背包型DP) 解题日志
逃亡的准备(hallows) 【问题描述】 在《Harry Potter and the Deathly Hallows》中,Harry Potter他们一起逃亡,现在有许多的东西要放到赫敏的包里面,但是包的大小有限…
蛙人(背包型DP) 解题日志
蛙人 (ple) 蛙人使用特殊设备潜水。设备中有一个气瓶,分两格:一格装氧气,另一格装氮气。留在水中有时间的限制,在深水中需要大量的氧气与氮气。为完成任务,蛙人必须安排好气瓶。每个气瓶可以用它的重量和含有气体的体积来描述…
质数和分解(背包型DP) 解题日志
质数和分解(prime) 【问题描述】 任何大于 1 的自然数 N,都可以写成若干个大于等于2且小于等于 N 的质数之和表达式(包括只有一个数构成的和表达式的情况),并且可能有不止一种质数和的形式。例如9 的质数和表达式…
采药(背包型DP) 解题日志
采药(medic) 【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药的山洞里对他说:“孩子,…
背包型DP【仅题目】
背包模型 采药(medic) 【问题描述】 辰辰是个天资聪颖的孩子,他的梦想是成为世界上最伟大的医师。为此,他想拜附近最有威望的医师为师。医师为了判断他的资质,给他出了一个难题。医师把他带到一个到处都是草药…
能量项链(区间型DP)解题日志
能量项链(energy) 【问题描述】 在Mars星球上,每个Mars人都随身佩带着一串能量项链。在项链上有n颗能量珠。能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。并且,对于相邻的两颗珠子,前一颗珠子的…