ICPC 2018 南京网络预赛 B The writing on the wall

【题目链接】

题目意思

给一个T表示案例个数，然后每个案例给出三个数字n(0 < n <= 100000),m(0 < m <= 100),k(0 < k <= 100000)，表示有n*m的方格，方格中有k个黑色方格，后面k行，每行给一个黑色方格的坐标(x,y)，其中保证(0

解题思路

暴力大法好。。。
up数组表示遍历到第i行时(即up更新第i次时)，每一列的黑格子所在的最高行

AC代码

#include <iostream>
#include <climits>
#include <algorithm>
#include <cstring>
using ll = long long;
using namespace std;
int e[100005][105], up[105];
int main()
{
    int t, n, m, k, a, b, ccase = 1;
    scanf("%d", &t);
    while (t--)
    {
        ll ans = 0;
        memset(e, 0, sizeof e);
        memset(up, 0, sizeof up);
        scanf("%d%d%d", &n, &m, &k);
        while (k--)
        {
            scanf("%d%d", &a, &b);
            e[a][b] = 1;
        }
        for (int i = 1; i <= n; i++)//枚举每一行
        {
            for (int j = 1; j <= m; j++)
                if (e[i][j])
                    up[j] = i;//更新值
            for (int j = 1; j <= m; j++)
            {
                ll temp = LLONG_MAX;//temp为了计算深度最大可以达到多少
                for (int k = j; k >= 1; k--)
                {
                    temp = min(temp, (ll)(i - up[k]));
                    ans += temp;
                }
            }
        }
        printf("Case #%d: %lld\n", ccase++, ans);
    }
}