本文共 7312 字，大约阅读时间需要 24 分钟。

最大子矩阵和

Description

给出一个N [2<=N<=100]，并给出一个N*N的矩阵，矩阵中的数为[-127,127]之间。求出矩阵中一块子矩阵的最大和。

比如：

0 -2 -7 0

9 2 -6 2

-4 1 -4 1

-1 8 0 -2

和最大的子矩阵应该是这个：

9 2

-4 1

-1 8

它的和是15。

Sample Input

4

0 -2 -7 0 9 2 -6 2 -4 1 -4 1 -18 0 -2

Sample Output

15

思路

第一个想法就是枚举每一个子矩阵，愉快TLE，然后我们用前缀和优化，再枚举，嗯，过了

设s[i][j]为第i行前j个的和，然后枚举一个区间（1<=i<=n,i<=j<=n),然后按最大序列和计算（设b[k]为从第一到第k列i，j区间的和.方程:$b[k]=b[k-1]+s[j][k]-s[i-1][k]$,(1<=k<=m)) 代码如下：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a[101][101],b[101],s[101][101];int main(){   	int n,m;	cin>>n;	m=n;	for (int i=1;i<=n;i++)	{   		for (int j=1;j<=m;j++) cin>>a[i][j],s[i][j]=s[i-1][j]+a[i][j];//前缀和	}	int ans=a[1][1];	for (int i=1;i<=n;i++)//枚举起点	{   		for (int j=i;j<=n;j++)//枚举终点		{   			int sum=0;			for (int k=1;k<=m;k++) b[k]=s[j][k]-s[i-1][k];//计算子矩阵和			for (int k=1;k<=m;k++)			{   				sum+=b[k];				if (sum>ans) ans=sum;				if (sum<0) sum=0;			}//找最大		}	}	cout<
       
      
     
    
   

也可以设f[i][j]为从1，1到i，j的前缀和，然后枚举每一个子矩阵求值

$f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j](1<=i<=n,1<=j<=n)$ 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

糖果盒

Description

一个被分为 n*m　个格子的糖果盒，第 i 行第 j 列位置的格子里面有 a [ i ][ j ] 颗糖。本来 tenshi 打算送这盒糖果给某 PPMM 的，但是就在要送出糖果盒的前一天晚上，一只极其可恶的老鼠夜袭糖果盒，有部分格子被洗劫并且穿了洞。tenshi 必须尽快从这个糖果盒里面切割出一个矩形糖果盒，新的糖果盒不能有洞，并且 tenshi 希望保留在新糖果盒内的糖的总数尽量多。

请帮tenshi设计一个程序 计算一下新糖果盒最多能够保留多少糖果。

Input

从文件CANDY.IN读入数据。第一行有两个整数 n、m。第 i + 1 行的第 j 个数表示 a [ i ][ j ]，如果这个数为 0 ，则表示这个位置的格子被洗劫过。其中：

1 ≤ n，m ≤ 300

0 ≤ a [ i ][ j ]≤ 255

Output

输出最大糖果数到 CANDY.OUT。

Sample Input

3 4

1 2 3 4 5 0 6 3 10 3 4 0

Sample Output

17

思路

这样的糖果都敢吃？

这就是子矩阵和的改版，只要把0都设为-无穷（够大就行）就可以了 设s[i][j]为第i行前j个的和，然后枚举一个区间（1<=i<=n,i<=j<=n),然后按最大序列和计算（设b[k]为从第一到第k列i，j区间的和.方程:$b[k]=b[k-1]+s[j][k]-s[i-1][k]$,(1<=k<=m)) 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a[1001][1001],b[1001],s[1001][1001];int main(){   	int n,m;	cin>>n>>m;	for (int i=1;i<=n;i++)	{   		for (int j=1;j<=m;j++)		{   			cin>>a[i][j];			if (a[i][j]==0) a[i][j]=-355*300*300;			s[i][j]=s[i-1][j]+a[i][j];		}	}	int ans=0;	for (int i=1;i<=n;i++)	{   		for (int j=i;j<=n;j++)		{   			int sum=0;			for (int k=1;k<=m;k++) b[k]=s[j][k]-s[i-1][k];			for (int k=1;k<=m;k++)			{   				sum+=b[k];				if (sum>ans) ans=sum;				if (sum<0) sum=0;			}		}	}	if (ans<=0) cout<<"NO";	else cout<
       
      
     
    
   

同样可以用枚举的方法

设f[i][j]为从1，1到i，j的前缀和，然后枚举每一个子矩阵求值 $f[i][j]=f[i-1][j]+f[i][j-1]-f[i-1][j-1]+a[i][j](1<=i<=n,1<=j<=n)$ 代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
      
     
    
   

打砖块

Description

KXT是一个很无聊的小朋友，一天到晚都在打坐…

一天，被他发现了一个比打坐更无聊的事情——打砖块。很多块砖分布在一个mm的矩阵中，他可以消掉以他为左上角顶点的一个nn的矩阵里的所有砖块。

喜欢偷懒的他请来了你帮他计算可以消掉最多的砖块数（只能消一次）。

Input

第一行：用空格隔开的三个整数n、m、k。

接下来k行，每行2个用空格隔开的整数Xi、Yi，表示第i块砖在Xi行、Yi列的位置。

Output

为可以消掉最多的砖块数。

Sample Input

5 10 11

　　2 1 　　4 6 　　4 9 　　3 9 　　9 7 　　9 9 　　7 9 　　8 10 　　8 8 　　8 6 　　10 2

Sample Output

6

Hint

【数据范围】

n<=m; k<=m*m

60%：n<=70; m<=70; k<=4900 100%：n<=1000; m<=1000; k<=1000000;

思路

这道题想不出来还来看我代码的人一定更无聊（手动狗头保命）

这道题目相当于一个给定大小的最大子矩阵和，这里我们可以用前缀和提速，直接枚举每一个矩阵 设b[1]为1至n行，1至n列的和，然后利用列前缀和求出b[2]~b[n-m+1](b[i]=b[i-1]-第i-1列前缀和+第i+m-1列前缀和（2<=i<=n-m+1）然后枚举行的起点（2<=i<=n-m+1）和列的起点（1<=j<=n-m+1）： $b[j]=b[j]-该方阵最上面的一行+最下面再下一行（i,j区间内）$ 输出其中的最大值 上代码：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a[1001][1001],b[1001],s[1001][1001],s2[1001][1001];int main(){   	int n,m,k;	cin>>m>>n>>k;	for (int i=1;i<=k;i++)	{   		int x,y;		scanf("%d%d",&x,&y);		a[x][y]=1;	}	for (int i=1;i<=n;i++)	{   		for (int j=1;j<=n;j++) s[i][j]=s[i][j-1]+a[i][j];//每一行的前缀和	}	for (int j=1;j<=n;j++)	{   		for (int i=1;i<=n;i++) s2[i][j]=s2[i-1][j]+a[i][j];//每一列的前缀和	} 	for (int i=1;i<=m;i++)	{   		b[1]+=s[i][m];	}//枚举子矩阵，这里是从上一个子矩阵推出这一个子矩阵	int ans=b[1];	for (int j=2;j<=n-m+1;j++)	{   		b[j]=b[j-1]-s2[m][j-1]+s2[m][j+m-1];		ans=max(ans,b[j]);	}	for (int i=2;i<=n-m+1;i++)	{   		for (int j=1;j<=n-m+1;j++)		{   			b[j]-=s[i-1][j+m-1]-s[i-1][j-1];			b[j]+=s[i+m-1][j+m-1]-s[i+m-1][j-1];			ans=max(ans,b[j]);		}	}	cout<
       
      
     
    
   

旅行

Description

ACM队员们到Z镇游玩，Z镇是一个很特别的城镇，它有m+1条东西方向和n+1条南北方向的道路，划分成MN个区域。Z镇的名胜位于这些区域内，从上往下第i行，从左往右数第j列的区域记为D（i,j）。ACM队员们预先对这MN个区域打分V(i,j)(分数可正可负)。分数越高表示他们越想到那个地方，越低表示他们越不想去。为了方便集合，队员们只能在某一个范围内活动。我们可以用(m1,n1)与(m2,n2)(m1<=m2，n1<=n2)表示这样一个范围：它是这些区域的集合： ，ACM队员希望他们活动区域的分值总和最大。

当然，有的队员可能一个也不去（例如，所有区域的分值都是负数。当然，如果某范围内的分值和为0的话，他们也不会去玩）。也有可能他们游览整个Z镇。你的任务是编写一个程序，求出他们的活动范围(m1,n1),(m2,n2)。

Input

输入有m+1行，第一行有两个整数m,n（m,n定义如上）。其中( )，接下来的m行，每行n个整数，第i行第j个数表示分数V(i,j)。（-128<=v(i,j)<=127）每两个整数之间有一个空格。

Output

输入只一行，分两种情况：

1． 队员在范围内(m1,n2)(m2,n2)内活动，输出该范围内的分值。

2． 队员们任何地方都不去，只需输出NO。

注意：不要输出多余的空行，行首行尾不要有多余的空格。

Sample Input

样例1

4 5 1 -2 3 -4 5 6 7 8 9 10 -11 12 13 14 -15 16 17 18 19 20 样例2 2 3 -1 -2 -1 -4 -3 -6

Sample Output

样例1

146 样例2 NO

思路

让你玩就不错了，还不想去

这道题和板子没什么大差别，就是answer小于等于0输出NO而已 设s[i][j]为第i行前j个的和，然后枚举一个区间（1<=i<=n,i<=j<=n),然后按最大序列和计算（设b[k]为从第一到第k列i，j区间的和.方程:$b[k]=b[k-1]+s[j][k]-s[i-1][k]$,(1<=k<=m))，如果其中最大的<=0,输出NO 代码来了：

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;int a[1001][1001],b[1001],s[1001][1001];int main(){   	int n,m;	cin>>n>>m;	for (int i=1;i<=n;i++)	{   		for (int j=1;j<=m;j++)		{   			cin>>a[i][j];			s[i][j]=s[i-1][j]+a[i][j];		}	}	int ans=0;	for (int i=1;i<=n;i++)	{   		for (int j=i;j<=n;j++)		{   			int sum=0;			for (int k=1;k<=m;k++) b[k]=s[j][k]-s[i-1][k];			for (int k=1;k<=m;k++)			{   				sum+=b[k];				if (sum>ans) ans=sum;				if (sum<0) sum=0;			}		}	}	if (ans<=0) cout<<"NO";	else cout<