洛谷题单--算法[2-1] 前缀和、差分与离散化_洛谷数列前缀和2

目录

0.铺垫学习：p1115最大子段和--前缀和+贪心+DP

1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩

---

0.铺垫学习：p1115最大子段和--前缀和+贪心+DP

原题链接：P1115 最大子段和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

原题：

题目描述

给出一个长度为 n 的序列 a，选出其中连续且非空的一段使得这段和最大。

输入格式

第一行是一个整数，表示序列的长度 n。

第二行有 n 个整数，第 i 个整数表示序列的第 i 个数字 ai​。

输出格式

输出一行一个整数表示答案。

输入输出样例

输入 

7
2 -4 3 -1 2 -4 3

输出

4

说明/提示

样例 1 解释

选取 [3,5]子段 {3,−1,2}其和为 4。

数据规模与约定

• 对于 40%40% 的数据，保证 n≤2×10。
• 对于 100%100% 的数据，保证 1≤n≤2×10，−10≤ai​≤10。

解法一：（精简版）

思路：

用到了前缀和+贪心的方法。

前缀和：

        用sum记录前缀和，一路循环累加过去，当sum变成负数时，继续循环到下一个数的时候就不要加上前面是负数的sum了（因为加上一个负数反而会变小，所以还不如不加），sum置为0，再继续累加。

贪心：

        用maxx来记录最大子段和，每一轮循环都比较maxx和sum，用maxx保留最大值，用sum去循环累加。

代码：

#include<iostream>
using namespace std;
int sum,maxx,j;
int main()
{
	int n;
	cin>>n>>maxx;
	sum=maxx;
	while(--n)
	{
		cin>>j;
		sum=sum>0?sum:0;
		sum+=j;
		maxx=maxx>sum?maxx:sum;
	}
	cout<<maxx;
}

解法二：（原理版） 

思路：

用暴力直接枚举 l,r ，求所有区间的和然后取最大值当然也可以，但是这道题会超时。所以我们来思考优化的方法。

首先，来看看这道题的例子：

2 -4 3 -1 2 -4 3
ans:4

发现选择区间[3,-1,2]是最优解，这是怎么推出来的呢？

首先让sum=第一个数2，下一个数是 -4 ，-4加上sum(值为2)=-2>-4，所以如果区间包括 -4 则一定会包括 2 此时更新sum=2+（-4）=-2

接下来 3 ，如果 3 加上前面的数 2 和 -4 则 sum=1，1<3，所以如果区间包括 3 则一定不会包括前面的 2 和 -4 （否则反而sum会小于3，所以还不如不加），前面的区间[2,-4]舍去。更新sum=3，区间更新为[3]

接下来是 -1 ，-1加上前面的区间[3]，sum=3+(-1)=2，2比 -1 大，所以如果区间包含 -1 则一定也会包含 3，更新sum=2，区间更新为[3,-1]

接下来是 2 ，2加上前面的区间[3，-1]，sum=sum+2=2+2=4，4比 2 大，所以如果区间包含 2 则一定也会包含 3和 -1，更新sum=4，区间更新为[3,-1,2]

接下来是 -4 ，-4 加上前面的区间[3，-1，2]，sum=sum+（-4）=4+（-4）=0，0比 -4 大，所以如果区间包含 -4 则一定也会包含 3， -1 和 2，更新sum=0，区间更新为[3,-1,2,-4]

最后是 3 ，3 加上前面的区间[3，-1，2，-4]，sum=sum+3=0+3=3，3等于3，所以最后这个3可加课不加，该题选择加上去，因为题目要求是连续的子段，如果后面还有数字可以让答案变得更大的话如果不加上这个3，那么两个子段就连不起来了，所以无脑加上。更新sum=0，区间更新为[3,-1,2,-4,3]

在推导的同时，我们用maxx来保留最大值，发现最大值是4，对应的子段是[3,-1,2]

总结一下过程：

• 第一个数是一个有效序列
• 如果一个数加上更新后的有效序列的值比这个数大，则该数加入有效序列
• 如果一个数加上更新后的有效序列的值比这个数小，则有效序列清空，再将该数加入有效序列
• 在执行上述过程中实时更新（DP）有效序列的所有元素之和并保留最大值

 代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n,sum,maxx;
	cin>>n>>maxx; 
	sum=maxx;// 把第一个数放入有效序列
	while(--n)
	{
		int a;
		cin>>a;
		sum=max(a,sum+a);
		maxx=max(sum,maxx);
	} 
	cout<<maxx;
}

---

1.p1719最大加权矩形--前缀和+贪心+DP+矩阵压缩

 原题链接：P1719 最大加权矩形 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

 原题：

题目描述

为了更好的备战 NOIP2013，电脑组的几个女孩子 LYQ,ZSC,ZHQ 认为，我们不光需要机房，我们还需要运动，于是就决定找校长申请一块电脑组的课余运动场地，听说她们都是电脑组的高手，校长没有马上答应他们，而是先给她们出了一道数学题，并且告诉她们：你们能获得的运动场地的面积就是你们能找到的这个最大的数字。

校长先给他们一个 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

和为 1515。

几个女孩子有点犯难了，于是就找到了电脑组精打细算的 HZH，TZY 小朋友帮忙计算，但是遗憾的是他们的答案都不一样，涉及土地的事情我们可不能含糊，你能帮忙计算出校长所给的矩形中加权和最大的矩形吗？

输入格式

第一行：n，接下来是 n 行 n 列的矩阵。

输出格式

最大矩形（子矩阵）的和。

输入输出样例

输入 

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

输出

15

说明/提示

1≤n≤120

 

思路：

总体思路其实就是第0题铺垫学习的内容再多加了一个压缩矩阵的操作。下面来讲解如何压缩矩阵，简单来说就是将二维的矩阵变成一维的，即数学里的化归的思想。

假设有一个矩阵：

9   2  -6  

-4  1  -4  

-1  8  0  

第一次我们取第一行：

9   2  -6  

其最大子序列和为 11（即9+2） ，max=11

第二次取第一、二行：

9   2  -6  

-4  1  -4  

注意！矩阵压缩的精髓来啦，我们将每一列的数字相加，将多行变为一行，即将二维变成一维了，这就是压缩。

第一列相加：9-4=5

第二列相加：2+1=3

第三列相加：-6-4=-10

所以压缩后的一维数组为：

5  3  -10

其最大子序列和为 8，max=11 不变

第三次取第一、二、三行：

9   2  -6  

-4  1  -4  

-1  8  0  

继续压缩，每列对应数字相加，将三维的压缩成一维

第一列相加：9-4-1=4

第二列相加：2+1+8=11

第三列相加：-6-4+0=-10

所以压缩后的一维数组为：

4  11  -10

其最大子序列和为 15，max=15

第四次取第二行：

-4  1  -4  

其最大子序列和为 1 ，max=15

第五次取第二、三行：

-4  1  -4  

-1  8  0  

第一列相加：-4-1=-5

第二列相加：1+8=9

第三列相加：-4+0=-4

 所以压缩后的一维数组为：

-5  9  -4

其最大子序列和为 9，max=15

第六次取第三行：

 -1  8  0  

其最大子序列和为 8，max=15

综上：

max=15，最大加权矩阵为 [(0,0)，(2,1)]：

9   2  

-4  1    

-1  8  

代码： 

#include<bits/stdc++.h>
using namespace std;
int n;
int ans=1<<31; // int型数据的最小值 
int ma[125][125];
int temp[125],dp[125];
 
void sum()
{
	memset(dp,0,sizeof(dp));
	dp[0]=temp[0];
	for(int i=1;i<=n;i++)
	{
		dp[i]=max(dp[i],dp[i-1]+temp[i]); // 前缀和+贪心--与题p1115（最大子串和）同理 
		ans=max(ans,dp[i]); // DP 
	}
}
 
void arrsum()
{
	for(int i=0;i<n;i++) // 压缩矩阵 
	{
		memset(temp,0,sizeof(temp));
		for(int j=i;j<n;j++) // 遍历矩阵的行
		{
			for(int k=0;k<n;k++) // 遍历矩阵的列 
			{
				temp[k]+=ma[j][k];
			}
			sum();
		}
	}
}
 
int main() 
{
	cin>>n;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			cin>>ma[i][j];
	arrsum();
	cout<<ans; 
}

 ps：如果代码里的 memset() 函数不清楚的朋友可以阅读下面这位大佬的文章，这里就不赘述。

        memset的用法详解-CSDN博客