动态规划及其应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,.,*,动态规划及其应用,赖国堃,福建师大附中,.,基本概念,动态规划问题的满足两个基本性质,一、最优子结构,问题可以表示为一些子问题，然后通过求解子问题的最优答案，得到问题答案。,二、无后效性,当前决策不会影响到之后的决策。,.,动态规划的3个基本要素,状态,转移,边界,这3个一般是做动态规划时要先思考清楚的问题。,.,例题,例,1,、数字三角形,（图,2,）示出了一个数字三角形。请编一个程序计算从顶至底的某处的一条路径，使该路径所经过的数字的总和最大。,每一步可沿左斜线向下或右斜线向下走；,1,三角形行数,100,；,三角形中的数字为整数,0,，,1,，,99,；,输入数据：,由,INPUT.TXT,文件中首先读到的是三角形的行数。,在例子中,INPUT.TXT,表示如下：,5,7,3 8,8 1 0,2 7 4 4,4 5 2 6 5,输出数据：,把最大总和（整数）写入,OUTPUT.TXT,文件。,上例为：,30,.,分析,只要对该题稍加分析，就可以得出一个结论：,如果得到一条由顶至底的某处的一条最佳路径，那么对于该路径上的每一个中间点来说，由顶至该中间点的路径所经过的数字和也为最大。因此该题是一个典型的多阶段决策最优化的问题。,我们采用动态规划中的顺推解法。按三角形的行划分阶段。若行数为n,则可把问题看作一个n-1个阶段的决策问题。从始点出发，依顺序求出第一阶段、第二阶段，第n-1阶段中各决策点至始点的最佳路径，最终求出始点到终点的最佳路径。,.,状态：fI,j表示，走到第i行第j列最大得分,转移：fI,j=fi-1,j-1+cI,j(j1),=fI-1,j+cI,j(j Listi,j.Tot)Then Listi,j.Tot:=Listi-1,j-1.Tot+Listi,j.Val;,若从i-1,j-1选择右斜线向下会使1,1至i,j的数字和最 大,则决策该步,If(j i)And(Listi-1,j.Tot+Listi,j.Val Listi,j.Tot)Then Listi,j.Tot:=Listi-1,j.Tot+Listi,j.Val,若从i-1,j选择左斜线向下会使1,1至i,j的数字和最大,则决策该步,End;for,.,例题,有一个体积为V背包，现在有n个物品，他们格子有自己的体积vi，和各自的价值wi。现在需要选出一些物品装进背包，你的任务是使装进物品的价值最大。,.,状态：fI,j(i表示处理第几个物品，j表示已用了多大空间),转移：fI,j=max(fi-1,j-vi+ci,fi-1,j),边界：f0,0=0;,.,for i:=1 to n do,for j:=1 to m do,begin,if j=vi then fi,j:=max(fi-1,j-vi+ci,fi-1,j),else fi,j:=fi-1,j;,end;,.,例题,【问题描述】,假设以最美观的方式布置花店的橱窗，有F束花，每束花的品种都不一样，同时，至少有同样数量的花瓶，被按顺序摆成一行，花瓶的位置是固定的，并从左到右，从1到V顺序编号，V 是花瓶的数目，编号为1的花瓶在最左边，编号为V的花瓶在最右边，花束可以移动，并且每束花用1到F 的整数惟一标识，标识花束的整数决定了花束在花瓶中列的顺序即如果I J，则花束I 必须放在花束J左边的花瓶中。例如，假设杜鹃花的标识数为1，秋海棠的标识数为2，康乃馨的标识数为3，所有的花束在放入花瓶时必须保持其标识数的顺序，即：杜鹃花必须放在秋海棠左边的花瓶中，秋海棠必须放在康乃馨左边的花瓶中。如果花瓶的数目大于花束的数目，则多余的花瓶必须空，即每个花瓶中只能放一束花。,.,每一个花瓶的形状和颜色也不相同，因此，当各个花瓶中放入不同的花束时会产生不同的美学效果，并以美学值(一个整数)来表示，空置花瓶的美学值为0。在上述例子中，花瓶与花束的不同搭配所具有的美学值，可以用如下表格表示。比如杜鹃花放在花瓶2中，会显得非常好看，但若放在花瓶4中则显得很难看。,.,为取得最佳美学效果，必须在保持花束顺序的前提下，使花的摆放取得最大的美学值，如果具有最大美学值的摆放方式不止一种，则输出任何一种方案即可。题中数据满足下面条件：1F100，FV100，50AIJ50，其中AII是花束I摆放在花瓶J中的美学值。输入整数F，V 和矩阵(AIJ)，输出最大美学值和每束花摆放在各个花瓶中的花瓶编号。,.,【,输入文件,】,第一行包含两个数：,F,，,V,。随后的,F,行中，每行包含,V,个整数，,Aij,即为输入文件中第（,i+1,）行中的第,j,个数,【,输出文件,】,包含两行,:,第一行是程序所产生摆放方式的美学值。第二行必须用,F,个数表示摆放方式，即该行的第,K,个数表示花束,K,所在的花瓶的编号。,【,输入样例,】,3 5,7 23 5 24 16,5 21-4 10 23,-21 5-4-20 20,【,输出样例,】,53,2 4 5,.,方法1,既然要拿花束一个一个的放，我们就以花束划分阶段。在这里，阶段变量k表示的就是要布置的花束数目（前k束花），状态变量s,k,表示第k束花所在的花瓶。而对于每一个状态s,k,，决策就是第k-1束花应该放在哪个花瓶，用u,k,表示。最优指标函数f,k,(s,k,)表示前k束花，其中第k束插在第s,k,个花瓶中，所能取得的最大美学值。,.,规划方程为：,（其中A(i,j)是花束i插在花瓶j中的美学值）,fI,j=max(fi-1,u+aI,j)(i=uj),.,方法2,以花瓶的数目来划分阶段。在这里阶段变量k表示的是要占用的花瓶数目（前k个花瓶），状态变量s,k,表示前k个花瓶中放了多少花。而对于任意一个状态s,k,，决策就是第s,k,束花是否放在第k个花瓶中，用变量u,k,=1或0来表示。最优指标函数f,k,(s,k,)表示前k个花瓶中插了s,k,束花，所能取得的最大美学值。,规划方程为：fI,j=max(fi-1,j,fi-1,j-1+aj,i),.,区间类动态规划,（,1,）,石子合并,【,问题描述,】,在一个圆形操场的四周摆放着,n,堆石子。现要,将,石子有次序地合并成一堆。规定每次只能选相邻的,2,堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将,n,堆石子合并成一堆的最小得分和最大得分。,【,输入文件,】,包含两行，第,1,行是正整数,n,（,1=n=100,），表示有,n,堆石子。第,2,行有,n,个数，分别表示每堆石子的个数。,【,输出文件,】,输出两行。第,1,行中的数是最小得分；第,2,行中的数是最大得分。,【,输入样例,】4,4 4 9 5,【,输出样例,】4354,.,分析,看到本题，容易想到使用贪心法，即每次选取相邻最大或最小的两堆石子合并。,然而这样做对不对呢？看一个例子。,6 3 4 6 5 4 2,如果使用贪心法求最小得分，应该是如下的合并步骤：第一次合并,3,4 6 5 4,2,2,3,合并得分是 第二次合并,5 4,6 5 4 5,4,合并得分是,9,第三次合并,9 6,5 4,5,4,合并得分是,9,第四次合并,9 6,9 9,6,合并得分是,15,第五次合并,15 9,15,9,合并得分是,24,总得分,5,9,9,15,24,62,但是如果采用如下合并方法，却可以得到比上面得分更少的方法：第一次合并,3 4,6 5 4 2 3,4,合并得分是,7,第二次合并,7 6,5 4 2 7,6,合并得分是,13,第三次合并,13 5,4 2,4,2,合并得分是,6,第四次合并,13,5 6,5,6,合并得分是,11,第五次合并,13 11,13,11,合并得分是,24,总得分,7,13,6,11,24,61,显然，贪心法是错误的。,为什么？,显然，贪心只能导致局部的最优，而局部最优并不导致全局最优。,.,具体来说我们应该定义一个数组,si,j,用来表示合并方法，,i,表示从编号为第,i,堆的石头开始合并，,j,表示从,i,开始数,j,堆进行合并，,si,j,为合并的最优得分。,则动规方程为：,SI,j,=,minsI,k+si+k,j-k+sumI,j,1=k=j-1,2=jn then t(i+k)mod n else ti+k 最后一个连第一个的情况处理 si,j最优si,k+st,j-k+sum1,3 sumi,j表示从i开始数j个数的和 end;,.,在,Mars,星球上，每个,Mars,人都随身佩带着一串能量项链。在项链上有,N,颗能量珠。能量珠是一颗有头标记与尾标记的珠子，这些标记对应着某个正整数。并且，对于相邻的两颗珠子，前一颗珠子的尾标记一定等于后一颗珠子的头标记。因为只有这样，通过吸盘（吸盘是,Mars,人吸收能量的一种器官）的作用，这两颗珠子才能聚合成一颗珠子，同时释放出可以被吸盘吸收的能量。如果前一颗能量珠的头标记为,m,，尾标记为,r,，后一颗能量珠的头标记为,r,，尾标记为,n,，则聚合后释放的能量为（,Mars,单位），新产生的珠子的头标记为,m,，尾标记为,n,。需要时，,Mars,人就用吸盘夹住相邻的两颗珠子，通过聚合得到能量，直到项链上只剩下一颗珠子为止。显然，不同的聚合顺序得到的总能量是不同的，请你设计一个聚合顺序，使一串项链释放出的总能量最大。例如：设,N=4,，,4,颗珠子的头标记与尾标记依次为,(2,，,3)(3,，,5)(5,，,10)(10,，,2),。我们用记号表示两颗珠子的聚合操作，,(,jk,),表示第,j,，,k,两颗珠子聚合后所释放的能量。则第,4,、,1,两颗珠子聚合后释放的能量为：,(41)=10*2*3=60,。这一串项链可以得到最优值的一个聚合顺序所释放的总能量为,(41)2)3,）,=10*2*3+10*3*5+10*5*10=710,。,.,【,输入文件,】,输入文件,energy.in,的第一行是一个正整数,N,（,4N100,），表示项链上珠子的个数。第二行是,N,个用空格隔开的正整数，所有的数均不超过,1000,。第,i,个数为第,i,颗珠子的头标记（,1iN,），当,i,时，第,i,颗珠子的尾标记应该等于第,i+1,颗珠子的头标记。第,N,颗珠子的尾标记应该等于第,1,颗珠子的头标记。至于珠子的顺序，你可以这样确定：将项链放到桌面上，不要出现交叉，随意指定第一颗珠子，然后按顺时针方向确定其他珠子的顺序。,【,输出文件,】,输出文件,energy.out,只有一行，是一个正整数,E,（,E2.1*109,），为一个最优聚合顺序所释放的总能量。,【,输入样例,】4 23510【,输出样例,】710,.,算法分析,如果要求一个链的最优合并方式,可以把这个链从中间断开,枚举断开处,分别求出,2,段的最优合并的值,再将这两端合并,而这条链断开后的,2,段的最优合并方式也可以用同样的方式计算,因此,本题具有最优子结构性质,可以用动态规划求解,但本题中并不是一个链而是一个环,但这并不影响最优子结构性质,可以做一条链,长度是环的,2,倍,其中前半段与后半段一样,都为环的顺序,(,可任意确定,),那么,从中间任取长度为,n,的一段,就实现了环的性质,首尾相接,.,设,fk,j,为从珠子,k,到珠子,j,的最优合并,那么枚举断开点,p,则,fk,j,的最优值为,fk,p,的最优值和,fp+1,j,的最优值的和再加珠子,k,p,和,p+1,j,合并的值,vk(k,的头标记,)*vp+1(p,的尾标记,=p+1,的头标记,)*vj+1(,即,j,的尾标记,),动规方程为,:,fk,j,=maxfk,p+fp+1,j+vk*vp+1*vj+1(kj2*n,且,k=pj),.,for d=1 to n /,从小到大枚举链的长度,for k=1 to 2*n do/,枚举链的起点,begin j=k+d-1;/,计算链的终点,if(j,=2*n)/,若在最大值范围内,for p=k to j-1/,枚举断开点,begin,根据方程更新,fk,j,的值,;end;end;,.,例题,1,、加分二叉树（,noip2003,）,【,问题描述,】,设一个,n,个节点的二叉树,tree,的中序遍历为（,l,2,3,n,），其中数字,1,2,3,n,为节点编号。每个节点都有一个分数（均为正整数），记第,i,个节点的分数为,di,，,tree,及它的每个子树都有一个加分，任一棵子树,subtree,（也包含,tree,本身）的加分计算方法如下：,subtree,的左子树的加分,subtree,的右子树的加分,subtree,的根的分数,若某个子树为空，规定其加分为,1,，叶子的加分就是叶节点本身的分数。不考虑它的空子树。,试求一棵符合中序遍历为（,1,2,3,n,）且加分最高的二叉树,tree,。要求输出；,（,1,）,tree,的最高加分,（,2,）,tree,的前序遍历,.,【,输入格式,】,第,1,行：一个整数,n,（,n,30,），为节点个数。,第,2,行：,n,个用空格隔开的整数，为每个节点的分数（分数,100,）。,【,输出格式,】,第,1,行：一个整数，为最高加分（结果不会超过,4,000,000,000,）。,第,2,行：,n,个用空格隔开的整数，为该树的前序遍历。,【,输入样例,】,5,5 7 1 2 10,【,输出样例,】,145,3 1 2 4 5,.,.,如果整棵树的权值最大，必然有左子树的权值最大，右子树的权值也最大，符合最优性原理,本题适合用动态规划来解。如果用数组,fi,j,表示从节点,i,到节点,j,所组成的二叉树的最大加分，枚举根节点，则动态方程可以表示如下：,fi,j,=,maxi,=t0 then begin dfs(l,i-1);s:=fl,i-1;end;/,处理左子树的加分,if,r-i,0 then begin dfs(i+1,r);if s0 then s:=s*fi+1,r else s:=fi+1,r;end;,inc(s,ai,);,if s,fl,r,then,begin,fl,r,:=s;,dl,r,:=i;end;,end;,end;,.,树形动态规划,顾名思义，树型动态规划就是在“树”的数据结构上的动态规划，平时作的动态规划都是线性的或者是建立在图上的，线性的动态规划有二种方向既向前和向后，相应的线性的动态规划有二种方法既顺推与逆推，而树型动态规划是建立在树上的，所以也相应的有二个方向：,1,、根,叶：不过这种动态规划在实际的问题中运用的不多，也没有比较明显的例题，所以不在今天讨论的范围之内。,2,、叶,根：既把根的子节点传递有用的信息给根，完成后根得出最优解的过程。这类的习题比较的多，下面就介绍一些这类题目和它们的一般解法。（树的后序遍历求解）,.,2、Ural 1018二叉苹果树,【,问题描述,】,有一棵苹果树，如果树枝有分叉，一定是分,2,叉（就是说没有只有,1,个儿子的结点）这棵树共有,N,个结点（叶子点或者树枝分叉点），编号为,1-N,树根编号一定是,1,。我们用一根树枝两端连接的结点的编号来描述一根树枝的位置。下面是一颗有,4,个树枝的树,2 5/3 4/1,现在这颗树枝条太多了，需要剪枝。但是一些树枝上长有苹果。给定需要保留的树枝数量，求出最多能留住多少苹果。,输入格式,第,1,行,2,个数，,N,和,Q(1=Q=N,1N=100),。,N,表示树的结点数，,Q,表示要保留的树枝数量。接下来,N-1,行描述树枝的信息。每行,3,个整数，前两个是它连接的结点的编号。第,3,个数是这根树枝上苹果的数量。每根树枝上的苹果不超过,30000,个。,输出格式,一个数，最多能留住的苹果的数量。,.,样例输入,5 21 3 11 4 102 3 203 5 20,样例输出,21,.,分析：,因为题目一给出就是纯二叉的树结构，如果要保留住最多苹果数量，必然是左子树保留尽量多，右子树也保留尽量多，满足最优性原理,我们定义状态,fi,j,表示以,i,为根的子树,(,还包括,i,与,i,的父亲,这条边,),内,保存,j,条边最多可以有多少苹果,显然,fi,j,=max(flefti,k+frighti,j-k-1)+applei,fatheri;,（,0=k=j-1,）,边界：,f0,i=0;fi,0=0;,问题的解：,f1,q+1;,虚拟了一条边，也就相当于多添加了一个节点,1,的父亲节点，这条边为,1,和它父亲节点的,.,procedure,tree_dp(t,k:integer,);,var i,ls,rs:integer;,begin,if,ft,k,0 then exit;,if(t=0)or(k=0)then,begin,ft,k,:=0;exit;,end;,ft,k,:=0;,for i:=0 to k-1 do,begin,tree_dp(treet.lc,i,);/,左子树,tree_dp(treet.rc,k-i-1);/,右子树,ls,:=,ftreet.lc,i,;/,记录左子树的值,rs,:=ftreet.rc,k-i-1;/,记录右子树的值,if,ft,k,ls+rs,then,ft,k,:=,ls+rs,;/,比较,end;,ft,k,:=,ft,k+treet.s,;/,保存最优值,end;,.,例题,问题描述,在大学里每个学生，为了达到一定的学分，必须从很多课程里选择一些课程来学习，在课程里有些课程必须在某些课程之前学习，如高等数学总是在其它课程之前学习。现在有,N,门功课，每门课有个学分，每门课有一门或没有直接先修课（若课程,a,是课程,b,的先修课即只有学完了课程,a,，才能学习课程,b,）。一个学生要从这些课程里选择,M,门课程学习，问他能获得的最大学分是多少？,输入：,第一行有两个整数,N,M,用空格隔开。,(1=N=200,1=M=150),接下来的,N,行,第,I+1,行包含两个整数,ki,和,si,ki,表示第,I,门课的直接先修课，,si,表示第,I,门课的学分。若,ki,=0,表示没有直接先修课（,1=,ki,=N,1=,si,=0 then exit;,treedp(ax.r,y,);,只有右子树的情况,j:=,bax.r,y,;,for k:=1 to y do,左右子树都有的情况,begin,treedp(ax.l,k-1);,treedp(ax.r,y-k,);,i:=bax.l,k-1+bax.r,y-k+ax.k;,if ij then j:=i;,end;,bx,y,:=j;,end;,.,begin,readln(s,);,assign(input,s);reset(input,);,readln(n,m,);,fillchar(f,sizeof(f),0);,for i:=0 to n do,begin,ai.l,:=-1;ai.r:=-1;ai.k:=-1;end;,建树,for i:=1 to n do,begin,readln(k,l,);,ai.k,:=l;,if,fk,=0 then,ak.l,:=i,else,afk.r,:=i;,fk,:=i;,end;,.,边界,for i:=-1 to n do,for j:=-1 to m do,if(i=-1)or(j=0)then,bi,j,:=0 else,bi,j,:=-1;,记忆化实现动规,treedp(a0.l,m);,输出,writeln(ba0.l,m);,end.,时间复杂度最大为,O(n3),思考,:,若本题加上选那些课程可得到这个最大学分,怎样修改程序？,.,4,、河流,(IOI2005),一颗有,N+1,个结点的树，树中的每个结点可能会生产出一些产品。这些产品要么就地加工（要有加工厂才行），要么运送到它的父亲结点那儿去。现在在整棵树的根结点处已经有了一个产品加工厂，而且所有的产品最终必须在某个加工厂加工才行。由于运费昂贵，不可能将所有的产品都运送到根节点处加工。现在决定在树中的某些结点新增总共,K,个加工厂，现在要你选择这,K,个加工厂的厂址。,假设结点,i,会生产出,Wi,吨产品，它的父结点是,Pi,。而它到它的父结点的路径的长度是,Ui,。运费的计算是每运送,1,顿的货物，每单位长度收取,1,的费用。根节点的编号为,0,。,.,例如下图，,0,节点是根节点，如果要新增两个工厂，最佳方案是建在,2,、,3,两个节点上，这样总的费用为：,1*1,（,1,号）,+1*3,（,4,号）,=4,.,分析：由于题目中给出的树是多叉树，不便于进行动态规划。我们先利用儿子兄弟表示法，将多叉树转化为二叉树,进行了相关的转化之后，设,f(i,j,k,),表示在新树中，以,i,结点为根的子树中，分配,k,个加工厂。并且离,i,结点最近的加工厂在,j,结点的情况下。,i,结点及其子树内的所有产品，加工所需要的费用。,转移方程很容易就可以写出来：,总时间复杂度为,O(N2K2),。,.,状态压缩动态规划,有一些问题却被认为很可能不存在有效的(多项式级的)算法，这里以对几个例题的剖析，简述状态压缩思想及其应用。,.,预备知识,名称,C/C+样式,Pascal样式,简记法则,按位与,&,and,全一则一，否则为零,按位或,|,or,有一则一，否则为零,按位取反,not,是零则一，是一则零,按位异或,xor,不同则一，相同则零,左移位,shl,a,shr,ak等价于a/2,k,.,引例,在,n*n(n20),的方格棋盘上放置,n,个车(可以攻击所在行、列)，求使它们不能互相攻击的方案总数。,.,分析,其实本题是一个简单的组合数学问题，因为每行有且仅有一个车，所以我们只要来考虑每行上列的问题，显然每列只能出现一次，这题答案就是n的一个全排列，为,P(n,n)=n!,当然这题还有状态压缩的解法。,.,分析,我们仍然一行一行放置。,取棋子的放置情况作为状态，某一列如果已经放置棋子则为1，否则为0。这样，一个状态就可以用一个最多20位的二进制数表示。,例如,n=,5,第1、3、4列已经放置，则这个状态可以表示为01101(从右到左)。设,f,s,为达到状态,s,的方案数，则可以尝试建立,f,的递推关系。,.,前两行在第3、4列放置了棋子(不考虑顺序，下同)，第三行在第1列放置；,前两行在第1、4列放置了棋子，第三行在第3列放置；,前两行在第1、3列放置了棋子，第三行在第4列放置。,.,.,这三种情况互不相交，且只可能有这三种情况，根据加法原理，,f,s,应该等于这三种情况的和。,根据上面的讨论思路推广之，得到引例的解决办法：,其中s的右起第i+1位为1,(,其实就是在枚举s的二进制表示中的1,),.,状态压缩具有良好的拓展性。,在n*n(n20)的方格棋盘上放置n个车，某些格子不能放，求使它们不能互相攻击的方案总数。,我们只需要在原题的程序中枚举添加1的位置的时候进行判断就行。,.,program p1;,const,max=1 shl 20;,var n,i,t,c,j,tmp,r:longint;,f,a:array0.maxof int64;,begin,assign(input,p1.in);a,reset(input);,readln(n);,fillchar(f,sizeof(f),0);,for i:=1 to n do /,读入及预处理,begin,ai:=0;,for j:=1 to n do /,如果第i行的某位为0,表示这位不能放置,begin,read(c);,ai:=ai shl 1;,if c=1 then,ai:=ai+1;,end;,end;,.,f0:=1;,for i:=1 to(1 shl n)-1 do,begin,t:=i;r:=0;,while t0 do/,计算状态i中1的个数，即可得到其为第几行,begin,inc(r);,t:=t-(t and-t);,end;,tmp:=i and ar;,t:=tmp;,while t0 do/,枚举状态tmp二进制表示中的1,begin,fi:=fi+fi xor(t and-t);,t:=t-(t and-t);,end;,end;,writeln(f(1 shl n)-1);,end.,.,当然这个问题也可以用容斥原理解决，但这个不是今天的主题，有兴趣的同学可以自己思考。,.,例题,有一个n*m的棋盘(n、m80,n*m80)要在棋盘上放k(k20)个棋子，使得任意两个棋子不相邻(4个方向）。求合法的方案总数,.,我们看到,n*m80,稍微,思考我们可以发现：9*9=8180，即如果n,m都大于等于9，将不再满足n*m80这一条件。所以，我们有n或m小于等于8，而2,8,是可以承受的！,.,我们假设mn，n是行数m是列数，则每行的状态可以用m位的二进制数表示,但是本题和例1又有不同：例1每行每列都只能放置一个棋子，而本题却只限制每行每列的棋子不相邻,上例中枚举当前行的放置方案的做法依然可行。我们用数组s保存一行中所有的num个放置方案，则s数组可以在预处理过程中用DFS求出，同时用c,i,保存第i个状态中1的个数以避免重复计算,.,开始设计状态。本题状态的维数需要增加，原因在于并不是每一行只放一个棋子，也不是每一行都要求有棋子，原先的表示方法已经无法完整表达一个状态。,我们用,f,i,j,k,表示第i行的状态为s,j,且前i行总共放置k个棋子（下面用pn代替原题中的k）的方案数。沿用枚举当前行方案的做法，只要当前行的放置方案和上一行的不冲突。微观地讲，就是要两行的状态s,1,和s,2,中没有同为1的位即可，亦即,s,1,and,s,2,=0,.,然而，虽然我们枚举了第i行的放置方案，但却不知道其上一行(第i-1行)的方案,为了解决这个问题，我们不得不,连第i-1行的状态一起枚举,，则可以写出递推式：,其中s1=0，即在当前行不放置棋子；,j和p是需要枚举的两个状态编号。,.,例题,给出一个n*m(n100,m10)的棋盘，一些格子不能放置棋子。求最多能在棋盘上放置多少个棋子，使得每一行每一列的任两个棋子间至少有两个空格。,题目来源：NOI2001炮兵阵地,.,仍然先用DFS搜出一行可能状态s，依旧用c数组保存s中1的个数，依照例1的预处理搞定不能放置棋子的格子（应该有这种意识）,问题是，这个题目的状态怎么选？继续像例2那样似乎不行，原因在于棋子的攻击范围加大了,.,但是我们照葫芦画瓢：例2的攻击范围只有一格，所以我们的状态中只需要有当前行的状态，再枚举上一行的状态即可进行递推；而本题攻击范围是两格，因此增加一维来表示上一行的状态。,.,用,f,i,j,k,表示第i行状态为s,j,、第i-1行状态为s,k,时前i行至多能放置的棋子数。则状态转移方程很容易写出：,同时我们可以用滚动数组优化空间。,.,