从连续最大和到最优子矩阵.doc

从连续最大和到最优子矩阵。2009-02-07 16:34声明：此为转载，此篇也在noi专刊上刊登过。 从连续最大和到最优子矩阵 郑州市第101中学 2009届学生：史 沛关键字：连续最大和 最优子矩阵 动态规划 矩阵数据压缩从这次省选落选后，我发现有两个东西是自己极为欠缺的：1、动态规划；2、矩阵的相关知识；所以，这次好好地学习了一下矩阵和动态规划相结合的一些知识。为了以后能够铭记在心，特写一篇论文，一来，帮助那些还不清楚的OIers；二来，供自己日后参看。 题记一、 数列的连续最大和在谈及最优子矩阵之前，我们先来做一些准备工作，即：数列的连续最大和，顾名思义，就是在一个长度为n的数列An中，求i，j（1=i=jbest then best:=temp; if temp0 then temp:=0;end;注意：红色循环体部分的顺序万万不可颠倒！问题拓展：在一个长度为n的数列An中，求m个连续子序列，使得这m个连续子序列的和最大，且m个子序列无公共元素。解决类似的问题，我们可以利用“加一维”的思想利用动态规划来解决。用ansi,j表示数列前j个元素中，i个无公共元素的子序列的最大和，且必须包含第j个元素，数组no存放数列元素，则状态转移方程为：ansi,j=maxansi,j-1+noj,ansi-1,k+noj (i-1=kansi,j then ansi,j:=ansi-1,k+noj; end; for i:=1 to n do if ansm,ibest then best:=ansm,i; 注意：红色部分为确定最大值的过程！因为ansi,j表示数列前j个元素中，i个无公共元素的子序列的最大和，且最大和不一定非要取完所有的元素，所以用一个循环来检测所有m的连续子序列的元素最大和，以确定全局最优值！二、 最优子矩阵有了前面的铺垫，我们就可以导论最优子矩阵的问题了，换句话说，最优子矩阵是建立在数列连续最大和的基础上的。所谓最优子矩阵，就是指在一个n*m二维的矩阵中，确定一个小的矩阵，使这个小矩阵中所有元素的和最大。思考一下最优子矩阵和连续最大和的异同：1、 所求的和都具有连续性；2、 连续最大和是一维问题，最优子矩阵是二维问题另外，对于一个矩阵而言，如果我们将连续k行的元素纵向相加，并对相加后所得的数列求连续最大和，则此连续最大和就是一个行数为k的最优子矩阵！由此，我们可以将二维的矩阵压缩成一维矩阵，转换为线性问题，从而求解。故问题的关键在于如何用高效的压缩方式存储、读取矩阵。下面具一个简单的例子。在一个一维的数列中，要想求从第i个元素到第j个元素的和，我们可以用这样的方法：设数组sumi表示从第1个到第i个元素的和，则：求从第i个元素到第j个元素的和，只需用sumj-sumi就足够了。由此推广到二维矩阵，设sumi,j表示矩阵第j列前i个元素的和，costi,j表示原始数据，则：压缩数据程序代码为：for i:=1 to n dofor j:=1 to m do sumi,j:=sumi-1,j+costi,j;下一个问题是，如何将数据从压缩的数组中读出。下面，我们来分析、推导一下：假设n=3的情况，不同的组合情况和数据处理方法如下表：(1=jbest then best:=temp; if tempansi,j then ansi,j:=ansi-1,k+noj; end;for i:=1 to n do if ansm,ibest then best:=ansm,i;writeln(best);close(output);end;=begininit;solve;end. program t3(input,output);最优子矩阵varcost,sum:array0.200,0.200 of longint;temp:array0.200 of longint;n,m:longint;=procedure init;vari,j:longint;beginassign(input,t3.in);assign(output,t3.out);reset(input);rewrite(output);readln(n,m);fillchar(cost,sizeof(cost),0);fillchar(sum,sizeof(sum),0);for i:=1 to n do begin for j:=1 to m do read(costi,j); readln; end;close(input);for i:=1 to n do for j:=1 to m do sumi,j:=sumi-1,j+costi,j;end;=procedure solve;vari,j,k,best,ans,tot:longint;begintot:=-maxlongint;for i:=n downto 1 do for j:=i-1 downto 0 do begin for k:=1 to m do tempk:=sumi,k-sumj,k; ans:=-maxlongint; best:=0; for k:=1 to m do begin inc(best,tempk); if bestans then ans:=best; if besttot then tot:=ans; end;writeln(tot);close(output);end;=begininit;solve;end. program t4(input,output);2个最优子矩阵varcost,sum:array0.200,0.200 of longint;temp:array0.200 of longint;n,m,tot:longint;=procedure solve;vari,j,k,x,best1,best2,ans1,ans2:longint;begintot:=-maxlongint;for x:=2 to n do begin ans1:=-maxlongint; for i:=x-1 downto 1 do for j:=i-1 downto 0 do begin for k:=1 to m do tempk:=sumi,k-sumj,k; best1:=0; for k:=1 to m do begin inc(best1,tempk); if best1ans1 then ans1:=best1; if best1ans2 then ans2:=best2; if best2tot then tot:=ans1+ans2; end;end;=procedure init;vari,j,swap:longint;take:array0.200,0.200 of longint;beginassign(input,t4.in);assign(output,t4.out);reset(input);rewrite(output);fillchar(sum,sizeof(sum),0);readln(n,m);for i:=1 to n do begin for j:=1 to m do read(costi,j); readln; end;close(input);for i:=1 to n do for j:=1 to m do sumi,j:=sumi-1,j+costi,j;solve;swap:=m;m:=n;n:=swap;fillchar(sum,sizeof(sum),