动态规划专题讲义.ppt

动态规划专题讲义
第1页，共74页，2022年，5月20日，15点16分，星期一
前言
本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.
第2页，共74页，2022年，5月20一
拦截导弹
拦截导弹（Noip2002）
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种导弹拦截系统 有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高 于前一发的高度。 某天，雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段，所以 只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度，计算这套系统最多能拦截多少导弹。
第15页，共74页，2022年，5月20日，15点16分，星期一
拦截导弹
状态的表示－f[i]，表示当第i个导弹必须选择时，前i个导弹最多能拦截多少。
每个导弹有一定的高度，当前状态就是以第i个导弹为最后一个打的导弹。以前状态就是在这个导弹以前打的那个导弹。
显然这是十分能够体现状态间的联系的题目。
back
第16页，共74页，2022年，5月20日，15点16分，星期一
最长公共子串
给出两个字符串序列。求出这样的一个最长的公共子串：子串中的每个字符都能在两个原串中找到，而且每个字符的顺序和原串中的顺序一致。
第17页，共74页，2022年，5月20日，15点16分，星期一
交错匹配
交错匹配（最长公共子串的改编）
给你两排数字,只能将两排中数字相同的两个位置相连,而每次相连必须有两个匹配形成一次交错,.
2 3 3 2 4 1 5 1 3 5 10
3 1 2 3 2 4 12 1 5 5 3
状态的表示－f[i,j]表示前i个第一排的数字和前j个第二排的数字搭配的最优值。
(第一组交错),枚举他的以前状态就有1 3之前会有一个最优值存在,因此可以由此得到3 1的最优值.
back
第18页，共74页，2022年，5月20日，15点16分，星期一
买车票
买车票(Ural1031)
Ekaterinburg城到Sverdlovsk城有直线形的铁路线。两城之间还有其他一些停靠站,总站数为N。各站按照离Ekaterinburg城的距离编号。Ekaterinburg城编号为1，Sverdlovsk城编号为N。
back
第19页，共74页，2022年，5月20日，15点16分，星期一
买车票
某两站之间车票价格由这两站的距离X决定.
当0<X<=L1时，票价为C1元.
当L1<X<=L2时，票价为C2元.
当L2<X<=L3时，票价为C3元.
当两站距离大于L3时没有直达票，所以有时候要买几
次票做几次车才行。
比如，在上面的例图中，2-6没有直达票，有几种买票
方法可以从2-6，其中一种是买C2元的2-3车票，再买
C3元的3-6车票。
back
第20页，共74页，2022年，5月20日，15点16分，星期一
买车票
给定起点站和终点站还有
L1,L2,L3,C1,C2,C3，求出要从
起点到终点最少要花多少钱.
怎么办
确定题目的当前状态与以前状态!
back
第21页，共74页，2022年，5月20日，15点16分，星期一
买车票
当前状态
以前状态
当前所在的某个车站
(收费).
back
第22页，共74页，2022年，5月20日，15点16分，星期一
买车票
预处理
很容易想出一个N^2的预处理,(费用是一样的啊 )因此在每种收费情况下,(N)的程序:
for j:=1 to 3 do
begin
k:=en-1;
for i:=en downto be do
begin
while (way[i]-way[k]<=l[j])and(k>=be) do dec(k);
p[i][j]:=k+1;
end;
end;
数组P[i