Description

给定一个网格，每个格子上有一个数字。一次操作可以将 \(r~\times~c\) 的一块矩形的数字减去 \(1\)。必须保证这个矩形中的数全部为正。每次操作的 \(r\) 和 \(c\) 必须保持不变。求最少操作次数

Input

第一行是两个整数 \(n,m\)，代表格子行列数

下面 \(n\) 行 \(m\) 列描述这个格子

Output

一行一个数字代表答案

Hint

\(1~\leq~n,m~\leq~100\)，数字和不超过 \(10^9\)

Solution

非常显然的想法是枚举 \(r,c\)，然后暴力的判断是否合法。枚举 \(r,c\) 的复杂度是 \(O(n^2)\)，暴力判断的复杂度为 \(O(n^2 \log^2 n)\)，总复杂度 \(O(n^4 \log^2 n)\)。

然后发现这个题目的特殊性质：行列不相关。即无论列选择多大，行的最优解是不变的。列得选择同理。证明上，可以考虑数学归纳法。显然选取列为 \(1\) 时能算出行的最优解。当选取列为 \(k\) 时的最优解已经算出时，考虑计算选取列为 \(k + 1\) 时的最优解。我们发现如果列为 \(k + 1\) 时是合法的，那么列为 \(k\) 时一定是合法的。同时这个条件也是必要条件。所以我们可以按照列选择 \(1\) 时枚举出行的最优解，行选择 \(1\) 时枚举出列得最优解。即可得到答案。

考虑检验是否合法时，可以使用二维树状数组维护差分从而支持区间减法。总复杂度 \(O(n^3 \log^2n)\)。可以通过本题。事实上，由于另一个方位是 \(1\)，所以可以直接维护一维树状数组做到 \(O(n^3 \log n)\)。然而要写两遍……

Code

#include 
    
     #include 
     
      #ifdef ONLINE_JUDGE#define freopen(a, b, c)#define printtime()#else#include 
      
       #define printtime() printf("Times used  = %ld ms\n", clock())#endif#define ci const int#define cl const long longtypedef long long int ll;namespace IPT {    const int L = 1000000;    char buf[L], *front=buf, *end=buf;    char GetChar() {        if (front == end) {            end = buf + fread(front = buf, 1, L, stdin);            if (front == end) return -1;        }        return *(front++);    }}template 
       
        inline void qr(T &x) {    char ch = IPT::GetChar(), lst = ' ';    while ((ch > '9') || (ch < '0')) lst = ch, ch=IPT::GetChar();    while ((ch >= '0') && (ch <= '9')) x = (x << 1) + (x << 3) + (ch ^ 48), ch = IPT::GetChar();    if (lst == '-') x = -x;}template 
        
         inline void ReadDb(T &x) {    char ch = IPT::GetChar(), lst = ' ';    while ((ch > '9') || (ch < '0')) lst = ch, ch = IPT::GetChar();    while ((ch >= '0') && (ch <= '9')) x = x * 10 + (ch ^ 48), ch = IPT::GetChar();    if (ch == '.') {        ch = IPT::GetChar();        double base = 1;        while ((ch >= '0') && (ch <= '9')) x += (ch ^ 48) * ((base *= 0.1)), ch = IPT::GetChar();    }    if (lst == '-') x = -x;}namespace OPT {    char buf[120];}template 
         
          inline void qw(T x, const char aft, const bool pt) { if (x < 0) {x = -x, putchar('-');} int top=0; do {OPT::buf[++top] = static_cast
          
           (x % 10 + '0');} while (x /= 10); while (top) putchar(OPT::buf[top--]); if (pt) putchar(aft);}const int maxn = 110;int n, m;int MU[maxn][maxn], CU[maxn][maxn], tree[maxn][maxn];inline int lowbit(ci x) {return x & -x;}int check(ci, ci);void insert(ci, ci, ci);int ask(ci, ci);int query(ci, ci);int main() { freopen("1.in", "r", stdin); qr(n); qr(m); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) qr(MU[i][j]); int r = n, c = m; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) CU[i][j] = MU[i][j] - MU[i - 1][j] - MU[i][j - 1] + MU[i - 1][j - 1]; while (check(r, 1) == -1) --r; while (check(1, c) == -1) --c; int sum = 0; for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) sum += MU[i][j]; qw(sum / (r * c), '\n', true); printtime();}int check(ci x, ci y) { int a = n - x + 1, b = m - y + 1, cnt = 0; memset(tree, 0, sizeof tree); for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) insert(i, j, CU[i][j]); for (int i = 1; i <= a; ++i) for (int j = 1; j <= b; ++j) { int k = ask(i, j); if (k < 0) return -1; cnt += k; insert(i, j, -k); insert(i + x, j, k); insert(i, j + y, k); insert(i + x, j + y, -k); } for (int i = 1; i <= n; ++i) for (int j = 1; j <= m; ++j) if (ask(i, j) != 0) return -1; return cnt;}void insert(ci x, ci y, ci v) { for (int i = x; i <= n; i += lowbit(i)) for (int j = y; j <= m; j += lowbit(j)) tree[i][j] += v;}int ask(ci x, ci y) { return query(x, y) - query(x - 1, y) - query(x, y - 1) + query(x - 1, y - 1);}int query(ci x, ci y) { int _ret = 0; for (int i = x; i; i -= lowbit(i)) for (int j = y; j; j -= lowbit(j)) _ret += tree[i][j]; return _ret;}