学步园

预处理保存下以(0,0)为左上角、(r, c)为右下角的矩形内梅子的个数，则以(r1,c1)为左上角、(r2,c2)为右下角的大矩形内梅子的个数为cnt[r2][c2] - cnt[r1-1][c2] - cnt[r2][c1-1] + cnt[r1-1][c1-1]，注意边界。预处理复杂度为O(n)，n为矩形格子总数。则可以在O(1)内判断某个区域内还有几个梅子。

状态和状态转移方程都比较好设计。

倒是有个奇怪的现象：我的记忆化搜索代码中，有两个被注释掉了的if语句。加上这两个if语句，运行时间会增加50%（从1.1s变为1.6s）。不知是什么原因。

Run TIme: 1.082s

#define UVa  "9-3.1629.cpp"     //Cake slicing

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

//Global Variables.
const int maxn = 20 + 5, INF = 1<<30;
int n, m, k;            //n:rows, m:columns
int cherry[maxn][maxn];
int d[maxn][maxn][maxn][maxn];
int cnt[maxn][maxn];
////

int areacnt(int r1, int c1, int r2, int c2) {       //count the # of cherries in range ((r1, c1),(r2,c2))
    int a=cnt[r2][c2], b=0, c=0, d=0;
    if(r1)
        b = cnt[r1-1][c2];
    if(c1)
        c = cnt[r2][c1-1];
    if(r1&&c1)
        d = cnt[r1-1][c1-1];
    return a - b - c + d;
}

int dp(int r1, int c1, int r2, int c2) {
    int& ans = d[r1][c1][r2][c2];
    if(ans != -1) return ans;

    if(areacnt(r1, c1, r2, c2) == 1) return ans = 0;
    else if(areacnt(r1, c1, r2, c2) == 0) return ans = INF;

    ans = INF;

    for(int i = c1; i < c2; i ++) {       //vertical cut
//        if(areacnt(r1, c1, r2, i) && areacnt(r1, i+1, r2, c2)) {
            int d1, d2, len;
            d1 = dp(r1, c1, r2, i);
            d2 = dp(r1, i+1, r2, c2);
            len = r2-r1+1;
            ans = min(ans, d1 + d2 + len);
//        }
    }
    for(int i = r1; i < r2; i ++) {       //horizontal cut
//        if(areacnt(r1, c1, i, c2) && areacnt(i+1, c1, r2, c2)) {
            int d1, d2, len;
            d1 = dp(r1, c1, i, c2);
            d2 = dp(i+1, c1, r2, c2);
            len = c2-c1+1;
            ans = min(ans, d1 + d2 + len);
//        }
    }

    return ans;
}


int main() {
    int kase = 1;
    while(scanf("%d%d%d", &n, &m, &k) != EOF) {
        memset(cherry, 0, sizeof(cherry));

        int r, c;
        for(int i = 0; i < k; i ++) {
            scanf("%d%d", &r, &c);
            cherry[r-1][c-1] = 1;
        }

        memset(cnt, 0, sizeof(cnt));
        int linecnt;
        for(int i = 0; i < n; i ++) {
            linecnt = 0;
            for(int j = 0; j < m; j ++) {
                linecnt += cherry[i][j];
                cnt[i][j] = linecnt;
                if(i) cnt[i][j] += cnt[i-1][j];
            }
        }
        memset(d, -1, sizeof(d));

        printf("Case %d: %d\n", kase ++, dp(0, 0, n-1, m-1));
    }

    return 0;
}