部分和思想及应用

1、部分和思想及应用一、 最大连续子序列和二、 最大K个连续子序列和（不重叠）三、 最大最大子矩阵问题一. 求一行数字的最大连续子序列的和1079【问题描述】求最大连续子序列的和【输入】第一行输入n(n<=100000),第二行为n个以空格分开的整数；【输出】求该序列中最大的连续子序列的和(不超过int)- 12 -【样例输入】 6 1 2 -5 6 7 8【样例输出】21【试题分析】1、阶段和状态： 以第i个数结尾的最大连续和序列，可能存在两种选择：情形一：只包含ai情形二：包含ai和以ai-1结尾的最大连续和序列设fi表示以第i个数结尾的最大连续和2、状态转移方程： 转移方程：fi=ma

2、xfi-1,0+ai初始化：f1=a1Answer=maxfi|1<=i<=n该算法的时间复杂度为o(n)3、核心子程序：#include <iostream>using namespace std;int a100001,f100001,i,j,n,maxx;int main() cin>>n; for(i=1;i<=n;i+)scanf("%d",&ai); for(i=1;i<=n;i+)fi=-0x7fffffff/2; /注意要初始化 for(i=1;i<=n;i+) fi=max(fi-1,0)+ai

3、; maxx=-0x7fffffff/2; for(i=1;i<=n;i+) if(fi>maxx)maxx=fi; cout<<maxx<<endl; return 0;注：由fi只与fi-1有关，可用一个变量滚动存储，动态求最大值。思考：如果要输出其中一个具体的子序列，该如何处理？扩展 最大M子段和（连续子序列长度不超过M）2209【问题描述】输入一个长度为的整数序列（A1,A2,An），从中找出一段连续的长度不超过M的子序列，使得这个序列的和最大。【输入】第一行为用空格分开的两个整数n,m。第二行为n个用空格分开的整数序列,每个数的绝对值都小于1000

4、。 【输出】文件输出仅一个整数表示连续的长度不超过M的最大子序列和。【样例输入】6 41 -3 5 1 -2 3【样例输出】7【数据范围】：50%的数据N,M<=10000；100%的数据N,M<=200000【试题分析】算法一枚举设 F(i)为以Ai结尾长度不超过M的最大子序和对于每个F(i)，从1到m枚举k的值，完成Aj的累加和取最大值。(可以先求部份和处理) O(n2)时间复杂度算法二队列优化记s(i)为前i个数的累加和，考虑用队列来维护决策值S(i-k)。每次只需要在队首删掉S(i-m-1)，在队尾添加S(i-1) 。但是取最小值操作还是需要O(n)时间复杂度的扫描。考察在

5、添加S(i-1)的时候，设现在队尾的元素是S(k)，由于k<i-1，所以S(k)必然比S(i-1)先出队。若此时S(i-1)<=S(k)，则S(k)这个决策永远不会在以后用到，可以将S(k)从队尾删除掉（此时队列的尾部形成了一个类似栈的结构）同理，若队列中两个元素S(i)和S(j)，若i<j且S(i)>=S(j)，则我们可以删掉S(i)（因为S(i)永远不会被用到）。此时的队列中的元素构成了一个单调递增的序列，即：S1<S2<S3<<Sk我们来整理在求F(i)的时候，用队列维护S(i-k)所需要的操作：若当前队首元素S(x)，有x<i-m，

6、则S(x)出队；直到队首元素S(x)有x>=i-m为止。若当前队尾元素S(k)>=S(i-1)，则S(k)出队；直到S(k)<S(i-1)为止。在队尾插入S(i-1)取出队列中的最小值，即队首元素。由于对于求每个F(i)的时候，进队和出队的元素不止一个。 但是我们可以通过分摊分析得知，每一个元素S(i)只进队一次、出队一次，所以队列维护的时间复杂度是O(n)。而每次求F(i)的时候取最小值操作的复杂度是O(1)，所以这一步的总复杂度也是O(n)。 综上所述，该算法的总复杂度是O(n)#include<iostream>using namespace std;int

7、 s200001,num200001,q200001,ans,i,n,m,head,tail,c;/num记录队列中元素的编号;q记录队列中元素的值int main() cin>>n>>m;ans=-0xfffffff;tail=1;head=1;qtail=0;numtail=0; for(i=1;i<=n;i+) cin>>c; si=si-1+c; /累加求和 if(ans<si-qhead)ans=si-qhead; while(qtail>=si&&tail>0)tail-;/队尾出队操作 tail+; qt

8、ail=si; /入队 numtail=i; while(numhead<=i-m)head+; /队首出队操作 cout<<ans<<endl; return 0;二求一行数字的最大k个子序列的和 1885【问题描述】输入一个长度为的整数序列（A1,A2,An），从中找出m个连续子序列，使得这m个连续子序列的和最大。 【输入】第一行为用空格分开的两个整数n,m(n<=1000,m<=200)。第二行为n个用空格分开的整数序列,每个数的绝对值都小于1000。 【输出】文件输出仅一个整数表示连续的长度不超过M的最大子序列和。【样例输入】 5 2 3 -2

9、 1 2 3【样例输出】9【题目分析】可将该问题转换为“资源分配类型dp” fij：表示以ai结尾分成j段的最大连续子序列和； si：表示从a1到ai之间数字的和；fij=maxfi-1j;fkj-1+si-sk(0<=k<=i-1)/不要第i个元素，要第i个元素并枚举它与前面几个组成一段#include <iostream>using namespace std;int n,m,f2011001,sum1001,a1001;int main() cin>>n>>m; sum0=0; for(int i=1;i<=n;i+) scanf(&

10、quot;%d",&ai);sumi=sumi-1+ai; memset(f,0,sizeof(f); for(int i=1;i<=m;i+) for(int j=i;j<=n;j+) fij=fij-1; for(int k=i-1;k<j;k+) if(fi-1k+sumj-sumk>fij) fij=fi-1k+sumj-sumk; cout<<fmn<<endl; return 0; 方法2:上面的方和是o(n3),可以这样考虑，对于第i个数，他有三种选择，一是不要，二是自成一段，三是与前面的成为一段。fij0：表示以

11、前i个数分成j段的最大连续子序列和且第i个数舍掉；fij1：表示以前i个数分成j段的最大连续子序列和且必含第i个数；fij0=maxfi-1j1; fi-1j0/不要第i个元素，最大值为要与不要第i-1个的最大值fij1=maxfi-1j1; fi-1j-10+ai/要第i个元素，最大值为与第i-1个合在一起（所以第i-1也要要）或自成一段（所以第i-1不能要且前i-1个分成了j-1段,ai是第j段的开始的第一个）最大值。请仔细体会这个思想，其在“筷子”那道题也有应用，同理，此类分配问题可以都按此考虑。下面使用了滚动数组来节约空间。#include <iostream>using

12、namespace std;int a1001;int dp22012;int n,m;int main()scanf("%d%d",&n,&m);for(int i=0; i<=n; +i)dp0i0=dp0i1=0;for(int i=1; i<=n; +i)scanf("%d",&ai);for(int i=1; i<=n; i+)for(int j=1; j<=m; +j)dpi%2j0=max(dp(i-1)%2j1,dp(i-1)%2j0);dpi%2j1=max(dp(i-1)%2j1+ai,

13、dp(i-1)%2j-10+ai);printf("%dn",max(dpn%2m0,dpn%2m1);三求一个最大子矩阵的和(一)（不知道矩阵大小）O(n3)【例题】最大子矩阵问题1642【问题描述】：给定一个二维的数组（含正数或负数），请从中找出和最大的子矩阵。例如：Input：输入部分第一行是一个正整数n,说明矩阵的大小。下一行后面跟着n*n的矩阵。矩阵中每个数字的范围为 -1000, 1000。 Output：输出其中最大子矩阵的和。Sample Input 40 -2 -7 09 2 -6 2-4 1 -4 1-1 8 0 -2Sample Output：15【数

14、据范围】 n<=300【试题分析】 此题是“最大连续子序列和”的扩展应用，对于只有一行的数据，可以通过fi=maxfi-1,0+aifi表示以ai结尾的最大连续子序列和，如要有多行，则同样可以利用该思想，将多行压缩成一行来处理。这样，枚举从第i行到第j行纵向叠加成（同列数据加在一起）一行处理，由于一行是o(n), 枚举是o(n2),所以是O(n3). 对于叠加，可以在输入时同时计算列方向的累加和，将矩阵aij改造成sij,其中sij=si-1j+aij,这样可快速取出i行到第j行纵向叠加和。【核心代码】#include <iostream>using namespace st

15、d;int sum,n,i,j,k,s301301,a301301,t;int main() cin>>n; for(i=1;i<=n;i+) for(j=1;j<=n;j+)cin>>aij; for(i=1;i<=n;i+)s1i=a1i; for(i=2;i<=n;i+) for(j=1;j<=n;j+) sij=si-1j+aij; /bij表示从第1行到第i行中第j列的所有元素之和 sum=-0x7fffffff; for(i=1;i<=n;i+) /阶段:起始行 for(j=i;j<=n;j+) /状态:结束行 t=

16、sj1-si-11; /初始化第1列的值（第i行到到第j行叠加在一起） for(k=2;k<=n;k+) /决策:第几列 t=max(t,0)+sjk-si-1k; if(t>sum)sum=t; cout<<sum<<endl; return 0;思考：如果要输出其中一个具体的矩阵，该如何处理？（二）求两个不相交子矩阵问题【例题】最大矩形2041【问题描述】:一个N*M的矩阵，每个格子里面有个整数（绝对值不大与10） ,每个子矩阵（至少包含一个元素）的价值就是它所包含的格子内的数的和。 现在求两个不相交的子矩阵(不包含相同的格子),使得他们的价值的乘积最大

17、。 例如： N=3 ， M=4，矩阵如图所示： 2 3 4 5 1 3 2 4 4 3 2 1 最大子矩阵值乘积为288。（左边两列的和为16，右边两列的和为18，结果为16*18=288）。【文件输入】:第一行有两个数字n, m ( n, m < 100)。以后的n行，每行有m个整数。【文件输出】：输出文件只有一个数，即两不相交子矩阵价值乘积的最大值。【样例输入1】1 7-9 -9 8 8 1 7 -4【样例输出1】:128【样例输入2】: 3 4 2 3 4 5 1 3 2 4 4 3 2 1 【样例输出2】: 288【问题分析】：在一个n*m二维的矩阵中，确定两个小的矩阵，使这两个

18、小矩阵中所有元素的总和最大，且两个矩阵无公共元素。既然是拓展，就与原问题有内在的联系，怎样的联系呢？我们先来看一下两个小矩阵的位置关系： 如图中，所有的情况无非两种而已。对于第一种情况，可以枚举分割线（图中横线）的坐标，设其坐标为x，x从2到n逐个枚举，则可求出1到x-1行的左右自矩阵、从x到n行的最优子矩阵，二者的和如果大于当前最优值则更新。对于第二种情况，只需将原始矩阵的行、列交换，然后重复第一种情况的步骤即可。【程序代码】：#include <iostream>using namespace std;int a101101,sum101101=0,ans=0,m,n;bool

19、 yes;void init() int i,j; cin>>n>>m; yes=true; for(i=1;i<=n;i+) for(j=1;j<=m;j+) scanf("%d",&aij); if(aij!=0)yes=false; void ready() int i,j; for(i=1;i<=n;i+) for(j=1;j<=m;j+)sumij=sumi-1j+aij;void get(int s,int t,int l,int r,int &mx,int &mi) int i,j,k,p

20、,q; mx=-0x7fffffff; mi=0x7fffffff; for(i=s;i<=t;i+) for(j=i;j<=t;j+) p=0;q=0; for(k=l;k<=r;k+) if(p<0)p=sumjk-sumi-1k; else p=p+sumjk-sumi-1k; if(q>0)q=sumjk-sumi-1k; else q=q+sumjk-sumi-1k; if(mx<p)mx=p; if(mi>q)mi=q; void dp() int a1,b1,a2,b2,k; ans=-0x7fffffff; for(k=1;k<=

21、m-1;k+) get(1,n,1,k,a1,a2); get(1,n,k+1,m,b1,b2); if(a1*b1>ans)ans=a1*b1; if(a2*b2>ans)ans=a2*b2; for(k=1;k<=n-1;k+) get(1,k,1,m,a1,a2); get(k+1,n,1,m,b1,b2); if(a1*b1>ans)ans=a1*b1; if(a2*b2>ans)ans=a2*b2; int main() init(); ans=0; if(!yes)ready();dp(); cout<<ans<<endl; s

22、ystem("pause"); return 0;（三）求指定大小为m*n的最大子矩阵问题轰 炸（BSOI1968）【问题描述】：公元3030前，地球与某银河系星球COW为争夺资源开战，通过情报得知COW星球全部力量位于该星的最大平原Grass上，所有军事人员全部驻扎在分布在平原上的基地里，你的任务是去轰炸这些基地，消灭有生力量。 【文件输入】：平原Grass呈方形，共有M行N列，基地分布在这些交叉点上，每个基地里有R个人（0 <= r <= 100）,你的炸弹威力也呈方形（有点怪！）大小为w行h列，范围内的所有人将被其消灭。【文件输出】：只有一行为一个炸弹可最

23、多消灭多少人。【样例输入】：2 2 （表示m,n）1 1 （表示w,h）2 0 (以下两行两列表示基地的分布)1 0【样例输出】：2【数据规模】： 对于80%数据,1 <= m,n <= 1000 对于100%数据, 1 <= m,n <= 3000 【问题分析】 Sij:表示左上角为(1,1),右下角为(i,j)的子矩阵的累加和 Sij=aij+si-1j+sij-1-si-1j-1 /aij为(I,j)位置的元素值,si-1j-1被算了两次所以要减去一次【核心代码】#include<iostream>using namespace std;int max

24、x,m,n,w,h,i,j,s30013001,a30013001;int main() cin>>m>>n>>w>>h; for(i=1;i<=m;i+) for(j=1;j<=n;j+) scanf("%d",&aij); for(i=1;i<=m;i+) for(j=1;j<=n;j+) sij=aij+si-1j+sij-1-si-1j-1; maxx=0; for(i=w;i<=m;i+)/枚举右下角座标（i,j） for(j=h;j<=n;j+) if(maxx<s

25、ij-sij-h-si-wj+si-wj-h) maxx=sij-sij-h-si-wj+si-wj-h; cout<<maxx<<endl; return 0;（四）所求为正方形情况；【模拟试题】盖房子(BSOI1697)Description： 永恒灵魂最近得到了面积为n*m的一大块土地（高兴ING_），他想在这块土地上建造一所房子，这个房子必须是正方形的。 但是，这块土地并非十全十美，上面有很多不平坦的地方（也可以叫瑕疵）。这些瑕疵十分恶心，以至于根本不能在上面盖一砖一瓦。 他希望找到一块最大的正方形无瑕疵土地来盖房子。 不过，这并不是什么难题，永恒灵魂在10分钟

26、内就轻松解决了这个问题。 现在，您也来试试吧。Input： 输入文件第一行为两个整数n,m（1<=n,m<=1000），接下来n行，每行m个数字，用空格隔开。0表示该块土地有瑕疵，1表示该块土地完好。 Output： 一个整数，最大正方形的边长。Sample Input： 4 40 1 1 11 1 1 00 1 1 01 1 0 1Sample Output： 2【核心代码】方法一：fij:表示以(i,j)为右下角盖房子的最大边长；lfij:表示从(i,j)这点向左最长为1的区间；upij:表示从(i,j)这点向上最长为1的区间；fij=minfi-1j-1+1, lfij,up

27、ij；（aij=1）answer=扫描所有点的最大值#include<iostream>using namespace std;int i,j,m,n,ans,f10011001=0;int lf10011001=0,up10011001=0,map10011001=0;int main() cin>>n>>m; for(i=1;i<=n;i+) for(j=1;j<=m;j+) scanf("%d",&mapij); for(i=1;i<=n;i+)lfi1=mapi1; for(i=1;i<=n;i+)

28、 for(j=2;j<=m;j+) if(mapij=0)lfij=0; else lfij=lfij-1+1; for(i=1;i<=m;i+)up1i=map1i; for(i=2;i<=n;i+) for(j=1;j<=m;j+) if(mapij=0)upij=0; else upij=upi-1j+1; for(i=1;i<=n;i+) for(j=1;j<=m;j+) fij=min(fi-1j-1+1,min(lfij,upij); ans=0; for(i=1;i<=n;i+) for(j=1;j<=m;j+) if(fij>

29、;ans)ans=fij; cout<<ans<<endl; system("pause"); return 0;方法二：fij:表示以(i,j)为右下角盖房子的最大边长；fij=minfi-1j-1,fi-1j,fij-1+1；（aij=1）answer=扫描所有点的最大值#include<iostream>using namespace std;int a10011001,f10011001,ans,n,m,i,j;int main() cin>>n>>m; for(i=1;i<=n;i+) for(j=

30、1;j<=m;j+)scanf("%d",&aij); ans=0; for(i=1;i<=n;i+) for(j=1;j<=m;j+) if(aij=1) fij=min(fi-1j,min(fi-1j-1,fij-1)+1; if(ans<fij)ans=fij; cout<<ans<<endl; system("pause"); return 0;(五)所求为矩形的情况；月饼盒（BSOI1751）【题目背景】：中秋节了，CCC老师决定去送礼。 【问题描述】：一个被分为 n*m个格子的月饼盒，第

31、 i 行第 j 列位置的格子里面有 a ij个月饼。本来CCC老师打算送这盒月饼给某人的，但是就在要送出月饼盒的前一天晚上，一只极其可恶的老鼠夜袭月饼盒，有部分格子被洗劫并且穿了洞。CCC老师必须尽快从这个月饼盒里面切割出一个矩形月饼盒，新的月饼盒不能有洞，并且CCC老师希望保留在新月饼盒内的月饼的总数尽量多。【题目任务】：请帮CCC老师设计一个程序 计算一下新月饼盒最多能够保留多少月饼。 【文件输入】:第一行有两个整数 n、m。第i+1行的第 j 个数表示 a ij，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中：1 n，m 300 , 0 a ij 255 【文件输出】：输出最大月

32、饼数【样例输入】：3 41 2 3 45 0 6 310 3 4 0【样例输出】：17Hint:10 3 4这个矩形的糖果数最大【试题分析】：本题是一个矩阵上的经典模型：最大子矩阵（最大全1子方阵，最大对角线为1的子矩阵等），通常对于子矩阵有O(n3)的算法，最高效率是O(n2)算法。针对本题，和求最大子矩阵稍有不一样的地方是最大权值的矩阵，但思路是一样的。有人将这类型题目归结为动态规划，其实应该不是完全意义上的动态规划。我们先来看这道题目的解法：其实我们用简单的枚举，可以得到O(n6)的算法：对于每一个格子（i,j），枚举以它为右下角，以K，L为左上角的所有非0格子组成的矩形内所有格子数的和

33、，从中取出一个最大的值。#include<iostream>using namespace std;int a301301,maxx,n,m,i,j,k,L,s;int f(int x1,int y1,int x2,int y2) int s,i,j; s=0; for(i=x1;i<=x2;i+) for(j=y1;j<=y2;j+) if(aij=0)return -0x7fffffff;/如果矩形中有一个0，则不符合要求 else s+=aij; return s;int main() cin>>n>>m; for(i=1;i<=n;

34、i+) for(j=1;j<=m;j+)scanf("%d",&aij); maxx=0; for(i=1;i<=n;i+) /右下角行坐标i for(j=1;j<=m;j+) /右下角列坐标i for(k=i;k>=1;k-) /左上角行坐标k for(L=j;L>=1;L-) /左上角列坐标 s=f(k,L,i,j); /计算（k,L）到(I,j)矩形所有格子数据和 if(s>maxx)maxx=s; /取最优 cout<<maxx<<endl; return 0;【优化一】O(n4)测试中，有同学靠此

35、不太复杂的程序（思想上和实现上都不复杂）得到60分，一个可观的分数。这个程序只用几分钟就可以做出来，比在那里缴尽脑汁去想数据规模，而最后1分也没得到的强多了，可见考试中这种复杂问题简单化是多么的重要。当然我不是叫大家不要去深入思考更为高效率的算法，毕竟得到更多的分数和满分是最好的了，如果我们花比较短的时间做出上面哪个程序，有它殿低，有时间我们再来想更加高效率的算法，不是更好吗？显然上面的程序有许多重复计算，如果我们能采用一些方法尽量避免重复计算，比如利用递推来利用以前计算的结果（这种思想很重要，很多问题都利用到这种思想，是优化算法的最高境界，动态规划就是这种思想的重要运用，hash表记录信息也

36、是利用这种思想）：如果我们用二维数组aij记录以（i,j）为右下角，以（1，1）为左上角的矩形内所有数的和，则计算aij就有递推公式：aij:=aij+ai-1j+aij-1-ai-1j-1（重要，后面的优化都是以此为基础）有了这个数组，我们计算以（i,j）为右下角，以(x,y)为左上角的矩形内所有数的就可以用公式：sum:=aij-ax-1j-aiy-1+ax-1y-1有了上面的信息记录，我们可以将上面的程序优化到O(n4)这里有个技巧：我们将为0的格子如果改成-（255*900+1），那么，我们就可以简化某个矩形0的格子的判断，因为一旦有个这个格子，那么矩形内所有格子的和就是负数，肯定不能

37、成为最大。#include<iostream>using namespace std;int a301301,n,m,ans;void init() int c,i,j; cin>>n>>m; memset(a,0,sizeof(a); for(i=1;i<=n;i+) for(j=1;j<=m;j+) scanf("%d",&c); if(c=0)c=-(255*900+1); aij=c+ai-1j+aij-1-ai-1j-1; /递推计算ai,j void dp() int i,j,x,y,maxx,sum; m

38、axx=0; for(i=1;i<=n;i+) /右下角行坐标i for(j=1;j<=m;j+) /右下角列坐标i for(x=i;x>=1;x-) /左上角行坐标k for(y=j;y>=1;y-) /左上角列坐标 sum=aij-ax-1j-aiy-1+ax-1y-1;/递推计算子矩阵 if(sum>ans)ans=sum;/选择最优 int main() init(); dp(); cout<<ans<<endl; return 0;【优化二】：O(n3)但是上面的程序还是不够理想，我们还可以继续优化：我们可以看到，上面的程序在枚举

39、矩形的时候是在盲目地枚举，如果我们只枚举以(i,j)为右下脚，不会含有的矩阵，将会提高效率，有了这个想法，我们设置一个数组bij来记录以第i行上，以(i,j)为最后一个格子，向左数连续不为的格子的个数。如下表：有了这个信息，我们在枚举以（i,j）为右下角的矩形时候，就利用b数组的信息，可以用一重循环枚举矩形的高，而宽可以由b数组一次性得到，由此我们得到O(n3)的算法：例如上面以（4，5）格子为右下脚的矩形：第次枚举高为的矩形：显然这个矩形的最大宽就是b45=4，第次枚举高为的矩形：显然这个矩形的最大宽是minb45，b35；#include<iostream>using name

40、space std;int a301301=0,b301301=0,n,m,ans;void init() int c,i,j; cin>>n>>m; for(i=1;i<=n;i+) for(j=1;j<=m;j+) scanf("%d",&c); aij=c+ai-1j+aij-1-ai-1j-1; if(c=0)bij=0; else bij=bij-1+1;/递推计算bI,j void dp() int i,j,L,h,maxx,sum; ans=0; for(i=1;i<=n;i+) for(j=1;j<=m;j+) if(bij>0) L=bij; maxx=aij-ai-1j-aij-L+ai-1j-L;/高为的矩阵 h=i-1; while(h>=1&&bhj>0)/高为i-h+1的矩阵 if(bhj<L)L=bhj; sum=aij-a