题解：CF2033B Sakurako and Water

原题链接

• 洛谷 CF2033B Sakurako and Water

解题思路

每个子矩阵的主对角线操作是相互独立的。

因此可以单独处理每条对角线。我们首先考虑每条对角线，找到该对角线上的最小值，然后将其提升到非负数，这样整条对角线上的所有值都变为非负。

将每个 $a_{i,j}$ 统计到其所在的对角线编号 $i-j+ n$。

对于每条对角线，如果最小值 $b_i$ 为负数，我们需要执行 $-b_i$ 次操作将其提升到非负值。

参考代码

#include <bits/stdc++.h>
using namespace std;

using ll=long long;
const int inf=0x3f3f3f3f;
const int mod=1e9+7;
const int N=505;
int a[N][N],b[N<<1];
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	int T;
	cin>>T;
	while(T--)
	{
		int n;
		cin>>n;
		for(int i=1;i<=(n<<1)-1;i++)
		{
			b[i]=inf;
		}
		for(int i=1;i<=n;i++)
		{
			for(int j=1;j<=n;j++)
			{
				cin>>a[i][j];
				b[i-j+n]=min(b[i-j+n],a[i][j]);
			}
		}
		int ans=0;
		for(int i=1;i<=(n<<1)-1;i++)
		{
			if(b[i]<0)ans-=b[i];
		}
		cout<<ans<<'\n';
	}
	return 0;
}