UVA1629 切蛋糕 Cake slicing

url: https://www.luogu.com.cn/problem/UVA1629

tag:
动态规划，枚举，前缀和

思路：
用 dp[lx][ly][rx][ry] 来记录某一个区间中，为使每一块蛋糕都有樱桃的最小代价。使用dfs来枚举每一种可能性。使用记忆化搜索来减少时间。前缀和快速计算出某一块区域樱桃的数量。

代码：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 30;
int dp[N][N][N][N];
int p[N][N];
int cs;
int pnum(int lx, int ly, int rx, int ry)
{
    return p[rx][ry] - p[lx - 1][ry] - p[rx][ly - 1] + p[lx - 1][ly - 1];
}
int DP(int lx, int ly, int rx, int ry)
{
    if (pnum(lx, ly, rx, ry) == 0) return 0x3f3f3f3f;
    if (pnum(lx, ly, rx, ry) == 1) return 0;
    int &d = dp[lx][ly][rx][ry];
    if (d != 0x3f3f3f3f) return d;
    for (int i = lx; i < rx; i ++)
        d = min(d, DP(lx, ly, i, ry) + DP(i + 1, ly, rx, ry) + ry - ly + 1);
    for (int i = ly; i < ry; i ++)
        d = min(d, DP(lx, ly, rx, i) + DP(lx, i + 1, rx, ry) + rx - lx + 1);
    return d;
}
int main()
{
    int n, m, k;
    while(scanf("%d%d%d", &n, &m, &k) != EOF && n && m)
    {
        memset(p, 0, sizeof p);
        for (int i = 0; i < k; i ++)
        {
            int a, b;
            scanf("%d%d", &a, &b);
            p[a][b] = 1;
        }
        for (int i = 1; i <= n; i ++)
            for (int j = 1; j <= m; j ++)
                p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
        memset(dp, 0x3f, sizeof dp);
        printf("Case %d: %d\n", ++cs, DP(1, 1, n, m));
    }
    return 0;
}