洛谷P2280 高维前缀和（平面矩阵）的边界问题

zclll

2022 年 03 月 28 日

1259 次浏览

暂无评论

1537字数

算法

## 题意

见[P2280 [HNOI2003]激光炸弹](https://www.luogu.com.cn/problem/P2280)

## 分析

题目本身并不难，二维矩阵区间和的问题，可以用二维前缀和解决，容斥一下就好，做法比较显然。当然，维度更高的时候就不能再简单容斥了，可以通过子集和DP去完成（sosdp），这个也比较显然，因为容斥的下标显然具有某种规律，利用这种规律的状压DP就称为子集和DP，这个我们以后再聊。

这里主要是有几个细节问题，一个是最早没有注意到应当从下标0就开始算前缀和的呆逼问题（因为不止1维了，下标为$(0,y)$或者$(x,0)$的位置显然也要算）。然后就是减去的时候的边界问题。

第2个问题是算前缀和的时候：

```cpp
FOR(i, 0, 5000)
FOR(j, 0, 5000)
	val[i][j] = val[i][j] + val[i - 1][j] + val[i][j - 1] - val[i - 1][j - 1];
```

这样显然是不行的。因为会越界。

第3个问题是求差分的时候：

```cpp
void update(int x, int y)
{
	int tmp = val[x][y];
	int xx = x - m, yy = y - m;
	if (yy >= 0)
		tmp -= val[x][yy];
	if (xx >= 0)
		tmp -= val[xx][y];
	if (xx >= 0 && yy >= 0)
		tmp += val[xx][yy];
	else if (xx >= 0)
		tmp += val[xx][0];
	else if (yy >= 0)
		tmp += val[0][yy];
	ans = max(ans, tmp);
}
```

最后两个else if是多余的。因为画图可知只有左上角坐标在界内才会多剪掉左上角的矩形（否则这个矩形根本不存在界内，就不会有任何多剪掉的部分）。

## 正解代码

```cpp
#include <bits/stdc++.h>
using namespace std;
#define mp(x, y) make_pair(x, y)
#define pb(x) push_back(x)
#define FOR(x, y, z) for (int x = y; x <= z; x++)
typedef long long ll;
typedef pair<int, int> pii;
int n, m;
#define N 5003
int val[N][N];
int ans = 0;
void update(int x, int y)
{
	int tmp = val[x][y];
	int xx = x - m, yy = y - m;
	if (yy >= 0)
		tmp -= val[x][yy];
	if (xx >= 0)
		tmp -= val[xx][y];
	if (xx >= 0 && yy >= 0)
		tmp += val[xx][yy];
	ans = max(ans, tmp);
}
int main()
{
	cin >> n >> m;
	FOR(i, 1, n)
	{
		int x, y, v;
		cin >> x >> y >> v;
		val[x][y] = v;
	}
	FOR(i, 0, 5000)
	FOR(j, 0, 5000)
	{
		if (i-1 >= 0)
			val[i][j] += val[i-1][j];
		if (j-1 >= 0)
			val[i][j] += val[i][j-1];
		if (i-1 >= 0 && j-1 >= 0)
			val[i][j] -= val[i-1][j-1];
		update(i, j);
	}
	cout << ans;
	return 0;
}
```