直接暴力定义f[x1][y1][x2][y2]是使对角为\((x1, y1),(x2, y2)\)这个子矩形满足要求的最短切割线长度

因为转移顺序不好递推，采用记忆化搜索

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #define LL long longusing namespace std;LL read() {    LL k = 0, f = 1; char c = getchar();    while(c < '0' || c > '9') {        if(c == '-') f = -1;        c = getchar();    }    while(c >= '0' && c <= '9')      k = k * 10 + c - 48, c = getchar();    return k * f;}int f[21][21][21][21], sum[21][21];bool mapp[21][21];int dp(int x1, int y1, int x2, int y2) {    int num = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];    if(num == 1) return f[x1][y1][x2][y2] = 0;    if(num == 0) return f[x1][y1][x2][y2] = 2147483647 / 3;        if(f[x1][y1][x2][y2] != -1) return f[x1][y1][x2][y2];        f[x1][y1][x2][y2] = 2147483647 / 3;    for(int i = x1; i < x2; ++i)        f[x1][y1][x2][y2] = min(dp(i+1, y1, x2, y2) + dp(x1, y1, i, y2) + abs(y1 - y2) + 1, f[x1][y1][x2][y2]);    for(int i = y1; i < y2; ++i)        f[x1][y1][x2][y2] = min(dp(x1, y1, x2, i) + dp(x1, i+1, x2, y2) + abs(x1 - x2) + 1, f[x1][y1][x2][y2]);    return f[x1][y1][x2][y2];}int n, m, k;void solve(int tot) {    memset(f, -1, sizeof(f));    memset(mapp, 0, sizeof(mapp));    for(int i = 1; i <= k; ++i) {        int x = read(), y = read();        mapp[x][y] = 1;    }    for(int i = 1; i <= n; ++i)        for(int j = 1; j <= m; ++j)            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + mapp[i][j];    dp(1, 1, n, m);    printf("Case %d: %d\n", tot, f[1][1][n][m]);}int main() {    int tot = 0;    while(scanf("%d %d %d", &n, &m, &k) != EOF)        solve(++tot);    return 0;}