线性动态规划

1、线性DP打鼹鼠（CSC WorkGroup邀请赛11,来自VIJOS）描述 Description根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会 在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网 格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一 时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网 格，即从坐标为（i,j）的网格移向（i-1, j）,（i+1, j）,（i,j-1）,（i,j+1）四个网格，机器人 不能走出整个n*n的网格。游戏开始时，你可以自由选定机器人

2、的初始位置。现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段 时间内打死尽可能多的鼹鼠。输入格式Input Format文件第一行为n（n=1000）, m（m0)and(y0)and(x=n)and(yfi thenif ai,1-aj,1=abs(ai,2-aj,2)+abs(ai,3-aj,3) then fi:=fj+1;for i:=1 to p doif fimax then max:=fi;end;procedure wf;beginassign(output,mole.out);rewrite(output);writeln(max);close

3、(output);end;beginrf;main;wf;end.Buy Low, Buy Lower (USACO )逢低吸纳“逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:”逢低吸纳，越低越买”这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则 购买股票的次数越多越好，看看你最多能按这个规则买几次。给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定 要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。以下面这个表为例，某几天的股价是：天数 1 2 3 4 5 6 7 8 9 10 11 12

4、股价 68 69 54 64 68 64 70 67 78 62 98 87这个例子中，聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低， 那么他最多能买4次股票。一种买法如下(可能有其他的买法)：天数2 5 6 10股价 69 68 64 62PROGRAM NAME: buylowINPUT FORMAT第1行：N (1 = N = 5000),表示能买股票的天数。第2行以下:N个正整数(可能分多行)，第i个正整数表示第i天的股价.这些正整数大小不会超过 longint(pascal)/long(c+).SAMPLE INPUT (file buylow.in)1268

5、 69 54 64 68 64 70 67 78 62 98 87OUTPUT FORMAT只有一行，输出两个整数：能够买进股票的天数长度达到这个值的股票购买方案数量在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同 的(只能算做一个解)。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算 一次。SAMPLE OUTPUT (file buylow.out)4 2知其然：第一问是经典的最长下降子序列问题，其状态转移方程为：fi=maxfj+1 (ji , sjsi)，第二问是问有多少种不同的最长序列：ni=sumnj - nk (ji, sjsi, fj+

6、1=fi)，其中 k 为满足 ki 且 fk=fi、sk=si的最大的 k。知其所以然：评价：当时就没想过多做一次DP。思考：引申：乘积最大(NOIP)知其然：规划方程：FI,J = MINFI-1,K*NUMK+1,J (I-1=K=J-1)边界值:F1,I := NUM1,I;FI，J表示前J个数字中添上I个乘号后得到的最小值。NUMI，J表示数字串第I位到第J位的数。知其所以然：评价：思考：一般来说，一些将一串东西按顺序分成M份这种类型的。引申： 看球巴士(VIJOS P1331)题目大意：两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘 若干辆巴士，同一辆巴士上的

7、人必须在队伍中是连续的。为了在车上不起冲突，希望两队的 支持者人数尽量相等，差至多是D。有一个例外，就是一辆车上的人全部都是一个球队的支 持者。问要将这N个人全部送至球场，至少要几辆巴士。知其然：设AI表示前I个人坐车，最少用多少辆车。AI:=MIN(AK+1)(K到I之间符合要求)知其所以然：与最长不下降数列相似。评价：时间复杂度还是很大的。思考：引申：过河(NOIP2005)(注意状态压缩)迎春舞会之三人组舞(VIJOS)题目大意：n个人选出3*m人，排成m组，每组3人。 站的队形较矮的2个人站两侧， 最高的站中间。从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度” 越低。

8、计算公式为h=(a-b广2 (a、b为较矮的2人的身高)现在候选人有n个人，要从他 们当中选出3*m个人排舞蹈，要求总体的“残疾程度”最低。知其然：设FI,J表示前J个人中组成I组的最低残疾FI,J:=MIN(FI,J-1,FI-1,J-2+SQR(AJ-1,AJ);A已有序。知其所以然：在相邻的中选择才会最小。评价：很不像我们以前做开那种，所以想不到思考：DP中很少有直接DP，要解决后效性，排序是一种很好的手段。引申：佳佳的筷子代码：varn,m:longint;a:array0.5000 of longint;f:array0.1000,0.5000 of longint;procedur

9、e readfile;vari,j:longint;beginassign(input,dance.in);reset(input);readln(m,n);for i:=n downto 1 do read(ai);close(input);end;function min(x,y:longint):longint;beginif x=i*3 thenbeginfi,j:=min(fi,j-1,fi-1,j-2+sqr(aj-1-aj);end;end;procedure writefile;vari,j:longint;beginassign(output,dance.out);rewri

10、te(output);writeln(fm,n);close(output);end;beginreadfile;main;writefile;end.双调旅行售货员问题(bitonic.pas/c/cpp)问题描述欧氏旅行售货员问题是对给定的平面上n个点确定一条连接这n个点的长度最短的哈密 顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不 等式性质的旅行售货员问题。它仍是一个NP完全问题。最短双调TSP回路是欧氏旅行售货 员问题的特殊情况。平面上n个点的双调TSP回路是从最左点开始，严格地由左至右直到最 右点，然后严格地由右至左直至最左点，且连接每一个点恰好一

11、次的一条闭合回路。给定平面上n个点，编程计算这n个点的最短双调TSP回路。输入数据第1行有1个正整数n(1=n=300),表示给定的平面上的点数。接下来的n行中，每 行2个实数，分别表示点的x坐标和y坐标。输出数据将计算的最短双调TSP回路的长度(保留2位小数)输出到文件。知其然：按横坐标排序。设FI,J表示分两条支路，一条到达i点，另一条到达j点的最小值。IJ；fj,i:=fj,i-1+dis(i,i-1);fi-1,i:=min(fi-1,i,fj,i-1+dis(j,i);知其所以然：之所以是线性dp，因为第i个点可以交接在第1到i-1个点上。由于fI,j=fj,i，所以规定 i=j；评

12、价：由红包那题联想出，如果能将点逆时针或顺时针排序，就好办。但实际不用。思考：排序解决后效性延伸：代码：typebb=array1.2 of real;vara:array0.300 of bb;f:array0.300,0.300 of real;n:longint;procedure sort(l,r:longint);varm:bb;mid1,mid2:real;i,j:longint;begini:=l;j:=r;mid1:=a(l+r) shr 1,1;mid2:=a(l+r) shr 1,2;repeatwhile (ai,1mid1)or(ai,1=mid1)and(ai,2mi

13、d1)or(aj,1=mid1)and(aj,2mid2) do j:=j-1;if i=j;if lj then sort(l,j);if iy then exit(y) else exit(x);end;procedure main;vari,j:longint;beginfillchar(f,sizeof(f),$7f);f0,0:=0;for i:=1 to n do f1,i:=dis(1,i);for i:=2 to n dobeginfor j:=1 to i-2 do fj,i:=fj,i-1+dis(i,i-1);for j:=1 to i-2 do fi-1,i:=min(fi-1,i,fj,i-1+d