前缀和

前缀和应用

Posted by zhangmh on 2021-11-24
Estimated Reading Time 4 Minutes
Words 950 In Total
Viewed Times

上一篇简单复习了一下前缀和的基础知识，做几个题练练手~

1273 WY的矩阵

img

学校oj上的一个题，思考方式有些不同，很容易看出是用DP做，但这个题也用到前缀和来完成。我们易知在一维数组中求连续子序列和最大值操作为：

1
2
3
4
for(int i=1;i<=n;i++)
{
	f[i]=max(a[i],f[i-1]+a[i]);
}

对于二维数组，我们采用的解决方法是：先求每一列的前缀和，这样相当于把二维数组压缩为一维数组，再在一维数组中用DP解决最大连续子序列和。

AC代码（解释都在注释里啦~）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=105;
int n;
int a[N][N];
int ans,s;

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=n;j++)
    	{
    		cin>>a[i][j];
    		a[i][j]+=a[i-1][j];//把输入的数组换为每一列的前缀和 
		}
	}
	ans=-1e9;//求最大值将答案初始化为最小值 
	for(int i=1;i<=n;i++)
	{
		for(int j=i;j<=n;j++)
		{
			s=0;
			for(int k=1;k<=n;k++)
			{
				s=max(s,0)+a[j][k]-a[i-1][k];//DP求一维数组最大连续子序列和 
				ans=max(ans,s);//比较得最大值 
			}
		} 
	}
	cout<<ans<<'\n';
	return 0;
}

P1387 最大正方形

img

洛谷上的题，数据范围比较小嘛，我的思路是这样的：暴力！

遍历二维矩阵，每到一个点改变正方形边长记录前缀和，最后输出某一矩阵区间的最大前缀和，满足这个前缀和等于边长的平方，，，就纯暴力做法，思路也很简单QAQ

下面放AC代码，具体细节在注释里：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <stack>
#include <vector>
#include <map>
#include <queue>
#include <cstring>
#include <cmath>
#include <set>
#include <iterator>

using namespace std;

typedef long long ll;
#define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define INF 0x3f3f3f3f
//判断是否需要开ll！！！
//判断是否需要初始化！！！
const int mod=1e9+7;
const int N=105;
int n,m,ans,d;
int a[N][N];
int dif[N][N];

int main()
{
//	freopen("test.in","r",stdin);
    cin>>n>>m;
    for(int i=1;i<=n;i++)
    {
    	for(int j=1;j<=m;j++)
    	{
    		cin>>a[i][j];
    		dif[i][j]=dif[i-1][j]+dif[i][j-1]+a[i][j]-dif[i-1][j-1];//初始化二维数组前缀和 
		}
	}
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=m;j++)
		{
			for(int k=0;k<=min(n-i,m-j);k++)//k为所加长度，但是注意，k不是边长，k+1才是！ 
			{                               //k的上限是i，j到边界的最小值，这样为了防止加上边长后超出矩阵范围 
				ans=dif[i+k][j+k]-dif[i-1][j+k]-dif[i+k][j-1]+dif[i-1][j-1];
				if(ans==(k+1)*(k+1))//满足正方形中没有0，即前缀和等于边长的平方 
				d=max(d,k+1);
			}
		}
	}
	cout<<d<<'\n';
	return 0;
}

但是我觉得这个题应该还有别的方法，，，我这个如果数据范围比较大就肯定会TLE，毕竟是O(n^3)的时间复杂度，，，我再想想QWQ

忘记了知识点就再做几个题回忆一下，多复习多复习~

若有错误请赐教 \ ^ _ ^ /

Orz

If you like this blog or find it useful for you, you are welcome to comment on it. You are also welcome to share this blog, so that more people can participate in it. If the images used in the blog infringe your copyright, please contact the author to delete them. Thank you !

FEATURED TAGS
前缀和
FRIENDS
ESC