线性DP
打鼹鼠（CSC WorkGroup 邀请赛II，来自VIJOS） 描述 Description
根据这个特点阿Q编写了一个打鼹鼠的游戏：在一个n*n的网格中，在某些时刻鼹鼠会在某一个网格探出头来透透气。你可以控制一个机器人来打鼹鼠，如果i时刻鼹鼠在某个网格中出现，而机器人也处于同一网格的话，那么这个鼹鼠就会被机器人打死。而机器人每一时刻只能够移动一格或停留在原地不动。机器人的移动是指从当前所处的网格移向相邻的网格，即从坐标为（i,j）的网格移向(i-1, j),(i+1, j),(i,j-1),(i,j+1)四个网格，机器人不能走出整个n*n的网格。游戏开始时，你可以自由选定机器人的初始位置。 现在你知道在一段时间内，鼹鼠出现的时间和地点，希望你编写一个程序使机器人在这一段时间内打死尽可能多的鼹鼠。 输入格式 Input Format
文件第一行为n（n<=1000）, m（m<=10000），其中m表示在这一段时间内出现的鼹鼠的个数，接下来的m行每行有三个数据time,x,y表示有一只鼹鼠在游戏开始后time个时刻，在第x行第y个网格里出现了一只鼹鼠。Time按递增的顺序给出。注意同一时刻可能出现多只鼹鼠，但同一时刻同一地点只可能出现一只鼹鼠。 输出格式 Output Format
输出文件中仅包含一个正整数，表示被打死鼹鼠的最大数目。 样例输入 Sample Input 2 2 1 1 1 2 2 2
样例输出 Sample Output 1
知其然：设F[I]表示到前I个鼹鼠能打死的MAX.
F[I]:=MAX{F[J]+1}，能在规定的时间内从第I只鼹鼠到达第J只鼹鼠。 知其所以然：其实就是LIS问题。
评价：代码要优秀，特别是已接近10的8次方的时候。多了一句话，就可能超时。 思考：要善于发现事物的本质。
引申：大地的秘密（将一串数排成规定的序列，每次只能移动临近的两个数，求最少移动次数。勇气的足迹仙剑模拟赛），合唱队形（NOIP2004），难解的问题（求解得的LIS必须有第K项。VIJOSP1369）. 代码： var
max,n,m,p:longint;
a:array[0..10000,1..3] of longint; f:array[0..10000] of longint; procedure rf; var
i,j,x,y,tt:longint; begin
assign(input,'mole.in'); reset(input); readln(n,m);
for i:=1 to m do begin
readln(tt,x,y);
if (x>0)and(y>0)and(x<=n)and(y<=n) then begin inc(p); a[p,1]:=tt; a[p,2]:=x; a[p,3]:=y; end; end;
close(input); end;
procedure main; var
i,j:longint; begin
for i:=1 to p do f[i]:=1; for i:=1 to p do
for j:=i-1 downto 1 do if f[j]+1>f[i] then
if a[i,1]-a[j,1]>=abs(a[i,2]-a[j,2])+abs(a[i,3]-a[j,3]) then f[i]:=f[j]+1; for i:=1 to p do
if f[i]>max then max:=f[i]; end;
procedure wf; begin
assign(output,'mole.out'); rewrite(output); writeln(max); close(output); end;
begin rf; main; wf; end.
Buy Low, Buy Lower （USACO）逢低吸纳 “逢低吸纳”是炒股的一条成功秘诀。如果你想成为一个成功的投资者，就要遵守这条秘诀:
\逢低吸纳,越低越买\
这句话的意思是：每次你购买股票时的股价一定要比你上次购买时的股价低.按照这个规则购买股票的次数越多越好，看看你最多能按这个规则买几次。
给定连续的N天中每天的股价。你可以在任何一天购买一次股票，但是购买时的股价一定要比你上次购买时的股价低。写一个程序，求出最多能买几次股票。 以下面这个表为例, 某几天的股价是: 天数 1 2 3 4 5 6 7 8 9 10 11 12
股价 68 69 54 64 68 64 70 67 78 62 98 87
这个例子中, 聪明的投资者(按上面的定义)，如果每次买股票时的股价都比上一次买时低，那么他最多能买4次股票。一种买法如下(可能有其他的买法): 天数 2 5 6 10 股价 69 68 64 62
PROGRAM NAME: buylow INPUT FORMAT
第1行: N (1 <= N <= 5000), 表示能买股票的天数。
第2行以下: N个正整数 (可能分多行) ，第i个正整数表示第i天的股价. 这些正整数大小不会超过longint(pascal)/long(c++). SAMPLE INPUT (file buylow.in) 12
68 69 54 64 68 64 70 67 78 62 98 87 OUTPUT FORMAT
只有一行，输出两个整数： 能够买进股票的天数
长度达到这个值的股票购买方案数量 在计算解的数量的时候，如果两个解所组成的字符串相同，那么这样的两个解被认为是相同的（只能算做一个解）。因此，两个不同的购买方案可能产生同一个字符串，这样只能计算一次。
SAMPLE OUTPUT (file buylow.out) 4 2
知其然：第一问是经典的最长下降子序列问题，其状态转移方程为：f[i]=max{f[j]}+1 (j
评价：当时就没想过多做一次DP。 思考： 引申：
乘积最大（NOIP） 知其然：规划方程: F[I,J] = MIN{F[I-1,K]*NUM[K+1,J]} (I-1<=K<=J-1)
边界值:F[1,I] := NUM[1,I];
F[I，J]表示前J个数字中添上I个乘号后得到的最小值。 NUM[I，J]表示数字串第I位到第J位的数。 知其所以然：
评价：
思考：一般来说，一些将一串东西按顺序分成M份这种类型的。 引申：
看球巴士（VIJOS P1331）
题目大意：两个球队的支持者要一起坐车去看球，他们已经排成了一列。我们要让他们分乘若干辆巴士，同一辆巴士上的人必须在队伍中是连续的。为了在车上不起冲突，希望两队的支持者人数尽量相等，差至多是D。有一个例外，就是一辆车上的人全部都是一个球队的支持者。问要将这N个人全部送至球场，至少要几辆巴士。 知其然：设A[I]表示前I个人坐车，最少用多少辆车。 A[I]:=MIN(A[K]+1)(K到I之间符合要求) 知其所以然：与最长不下降数列相似。 评价：时间复杂度还是很大的。 思考：
引申：过河（NOIP2005）（注意状态压缩）
迎春舞会之三人组舞（VIJOS）
题目大意：n个人选出3*m人，排成m组，每组3人。 站的队形——较矮的2个人站两侧，最高的站中间。从对称学角度来欣赏，左右两个人的身高越接近，则这一组的“残疾程度”越低。计算公式为 h=(a-b)^2 (a、b为较矮的2人的身高)现在候选人有n个人，要从他们当中选出3*m个人排舞蹈，要求总体的“残疾程度”最低。 知其然：设F[I,J]表示前J个人中组成I组的最低残疾??
F[I,J]:=MIN(F[I,J-1],F[I-1,J-2]+SQR(A[J-1],A[J])); A已有序。
知其所以然：在相邻的中选择才会最小。
评价：很不像我们以前做开那种??，所以想不到??
思考：DP中很少有直接DP，要解决后效性，排序是一种很好的手段。 引申：佳佳的筷子 代码：
var
n,m:longint;
a:array[0..5000] of longint;
f:array[0..1000,0..5000] of longint; procedure readfile; var
i,j:longint; begin
assign(input,'dance.in'); reset(input); readln(m,n);
for i:=n downto 1 do read(a[i]); close(input); end;
function min(x,y:longint):longint; begin
if x procedure main; var i,j:longint; begin for i:=1 to m do for j:=1 to n do f[i,j]:=maxlongint; for i:=1 to m do for j:=1 to n do if j>=i*3 then begin f[i,j]:=min(f[i,j-1],f[i-1,j-2]+sqr(a[j-1]-a[j])); end; end; procedure writefile; var i,j:longint; begin assign(output,'dance.out'); rewrite(output); writeln(f[m,n]); close(output); end; begin readfile; main; writefile; end. 双调旅行售货员问题(bitonic.pas/c/cpp) [问题描述] 欧氏旅行售货员问题是对给定的平面上n个点确定一条连接这n个点的长度最短的哈密顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不等式性质的旅行售货员问题。它仍是一个NP完全问题。最短双调TSP回路是欧氏旅行售货员问题的特殊情况。平面上n个点的双调TSP回路是从最左点开始，严格地由左至右直到最右点，然后严格地由右至左直至最左点，且连接每一个点恰好一次的一条闭合回路。 给定平面上n个点，编程计算这n个点的最短双调TSP回路。 [输入数据]