begin
for i:=be+1 to cl[st]-1 do
if a[i]^.s=a[cl[st]]^.s then begin dec(cl[st]);exit; end; bool(be,st); end;
{扩展产生新节点}
procedure expand(be,st:integer); var i,j,k,lx,ld:integer; begin
inc(op[st]);d:=a[op[st]]^.s; k:=a[op[st]]^.x;ld:=length(d); for i:=1 to mark do begin lx:=length(x[i,st]); for j:=1 to ld do begin
if (copy(d,j,lx)=x[i,st]) then begin if (st<>1)or(k<>4)then begin inc(cl[st]); new(a[cl[st]]); end;{if}
a[cl[st]]^.s:= copy(d,1,j-1)+ x[i,1-st]+ copy(d,j+lx,ld); a[cl[st]]^.x:=k+1;
check(be,st);{检查是否重复} end;{if} end;{for} end;{for} end;
procedure bfs;
var be,k,st:integer; Begin
for st:=0 to 1 do begin
if st=0 then be:=0 else be:=mid; op[st]:=be+0;cl[st]:=be+1; new(a[cl[st]]);
a[cl[st]]^.s:=x[0,st]; a[cl[st]]^.x:=0; end;{for} repeat
if (op[0]
(a[cl[1]]^.x>5); End; BEGIN
init;bfs;writeln('NO ANSWER!') END.
两种搜索算法的比较： 搜索方式 扩展方式 深度优先 后产生先扩展 广度优先 先产生先扩展 数据结构 适合求解的问题 栈 队列 可行解或所有解 最优解 在选择搜索方式时，并不是完全遵循以上原则，具体还是要根据题目的要求而定。在求最优解时，如果搜索的深度不大，我们也可以考虑使用深度优先搜索；在求解可行解时，如果搜索的深度没有限制，或者搜索的代价与搜索的深度成正比,我们也应该使用广度优先搜索。
算法在信息学奥赛中的应用（动态规划法）
在学习动态规划法之前，我们先来了解动态规划的几个概念
1、 阶段：把问题分成几个相互联系的有顺序的几个环节，这些环节即称为阶段。 2、 状态：某一阶段的出发位置称为状态。
3、 决策：从某阶段的一个状态演变到下一个阶段某状态的选择。
4、 状态转移方程：前一阶段的终点就是后一阶段的起点，前一阶段的决策选择导
出了后一阶段的状态，这种关系描述了由k阶段到k+1阶段状态的演变规律，称为状态转移方程。
动态规划法的定义：在求解问题中，对于每一步决策，列出各种可能的局部解，
再依据某种判定条件，舍弃那些肯定不能得到最优解的局部解，在每一步都经过筛选，以每一步都是最优解来保证全局是最优解，这种求解方法称为动态规划法。
一般来说，适合于用动态规划法求解的问题具有以下特点：
1、可以划分成若干个阶段，问题的求解过程就是对若干个阶段的一系列决策过
程。
2、每个阶段有若干个可能状态
3、一个决策将你从一个阶段的一种状态带到下一个阶段的某种状态。 4、在任一个阶段，最佳的决策序列和该阶段以前的决策无关。
5、各阶段状态之间的转换有明确定义的费用，而且在选择最佳决策时有递推关系
（即动态转移方程）。
动态规划法所处理的问题是一个多阶段最优化决策问题，一般由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，
同时确定了完成整个过程的一条活动路线。如下图：
动态规划设计都有着一定的模式，一般要经历以下几个步骤： 1、划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。
2、确定状态：将问题发展到各个阶段时所处的各种客观情况用不同的状态表示出来。
3、确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态，所以如果确定了决策，状态转移方程也就可以写出。
4、寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件
或边界条件。
5、程序设计实现：动态规划的主要难点在于理论上的设计，一旦设计完成，实现
部分就会非常简单。
根据以上的步骤设计，可以得到动态规划设计的一般模式： for k:=阶段最小值to 阶段最大值do {顺推每一个阶段}
for I:=状态最小值to 状态最大值do {枚举阶段k的每一个状态}
for j:=决策最小值to 决策最大值do {枚举阶段k中状态i可选择的每一种决策}
f[ik]:=min（max）{f[ik-1]+a[ik-1，jk-1]|ik-1通过决策jk-1可达ik}
有了以上的设计模式，对于简单的动态规划问题，就可以按部就班地进行动态规划设计。
动态规划算法应用
例1：合唱队形（noip2004tg）
【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, …, K，他们的身高分别为T1, T2, …, TK，则他们的身高满足T1 < T2 < … < Ti , Ti > Ti+1 > … > TK (1 <= i <= K)。你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。 【输入文件】输入文件chorus.in的第一行是一个整数N（2 <= N <= 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 <= Ti <= 230）是第i位同学的身高（厘米）。
【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。 【样例输入】8
186 186 150 200 160 130 197 220
【样例输出】 4
算法分析：此题采用动态规划法求解。先分别从左到右求最大上升子序列，从右到左求最大下降子序列，再枚举中间最高的一个人。算法实现起来也很简单，时间复杂度O(N^2)。
我们先考虑如何求最大上升子序列的长度，设f1(i)为前i个同学的最大上升子序列长度。若要求f1(i)，必须先求得f1(1),f1(2),…,f1(i-1)，再选择一个最大的f1(j)（j 设f2(i)为后面N-i+1位排列的最大下降子序列长度，用同样的方法可以得到状态转移方程：f2(i)=max{f2(j)+1} (i t,f1,f2:array[1..100]of byte; i,j,n,max:integer; begin assign(input,'chorus.in'); reset(input); readln(n); for i:=1 to n do begin read(t[i]);f1[i]:=1;f2[i]:=1; end;{for} close(input); max:=0; for i:=2 to n do for j:=1 to i-1 do begin if (t[i]>t[j])and(f1[j]>=f1[i]) then f1[i]:=f1[j]+1; {从左到右求最大上升子序列} if (t[n-i+1]>t[n-j+1])and(f2[n-j+1]>=f2[n-i+1]) then f2[n-i+1]:=f2[n-j+1]+1; {从右到左求最大下降子序列} end;{for} for i:=1 to n do if max 运用动态规划法求解问题的关键是找出状态转移方程，只要找出了状态转移方程，问题就解决了一半，剩下的事情就是解决如何把状态转移方程用程序实现。 例2、乘积最大（noip2000tg） 题目大意：在一个长度为N的数字串中插入r个乘号，将它分成r+1个部分，找出一种分法，使得这r+1个部分的乘积最大。 算法分析：此题满足动态规划法的求解标准，我们把它按插入的乘号数来划分阶段，若插入K个乘号，可把问题看做是K个阶段的决策问题。设f[i,k]表示在前i位数中插入K个乘号所得的最大值，a[i,j]表示从第i位到第j位所组成的自然数。用f[i,k]存储阶段K的每一个状态，可以得状态转移方程： f[i,k]=max{f[j,k-1]*a[j+1,i]}（k<=j<=i） 边界值：f[j,0]=a[1,j] (1 根据状态转移方程，我们就很容易写出动态规划程序： for k:=1 to r do for i:=k+1 to n do for j:=k to I do if f[i,k] 近年来，涉及动态规划的各种竞赛题越来越多，每一年的NOIP都至少有一道题目需要用动态规划法求解。而应用动态规划法解题是富于技巧性和创造性的，虽然在前面的求解过程中给出了一个解题的基本模式，但由于动态规划题目出现的形式多种多样，并且大部分题目表面上看不出与动态规划的直接联系，只有在充分把握其思想精髓的前提下大胆联想，多做多练才能达到得心应手，灵活运用的境界。
信息学奥赛 - 算法入门教程
