题解：CF2033B Sakurako and Water

题目链接

• 洛谷 CF2033B Sakurako and Water

解题思路

因为只需要不小于零就可以了，所以想到每次可以选中完整的对角线。

于是代价就变成了每条从左上到右下的斜线上最小的值的绝对值（如果最小值是整数则为零）。

之后只要遍历每条斜线找出代价并累积就好了。

参考代码

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

int T , n , a[N][N] , ans = 0;

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> T;
    while(T--)
    {
        ans = 0;
        cin >> n;
        for(int i = 1 ; i <= n ; i++)
        {
            for(int j = 1 ; j <= n ; j++)
            {
                cin >> a[i][j];
            }
        }
        for(int i = 2 ; i <= n ; i++)
        {
            int minn = 0;
            for(int j = 1 ; j <= i ; j++)
            {
                minn = min(minn , a[i - j][n - j + 1]);
            }
            ans -= minn;
        }
        for(int i = 0 ; i < n ; i++)
        {
            int minn = 0;
            for(int j = 1 ; j <= n - i ; j++)
            {
                minn = min(minn , a[i + j][j]);
            }
            ans -= minn;
        }
        cout << ans << endl;
    }
    //system("pause");
    return 0;
}