思路：dp(x, y, k, h)表示一个矩形，左上角坐标为(x, y)，宽为k，长为h，让该矩形切分为每块只有一个cake的最小长度。
模拟切蛋糕：横着切，竖着切，记忆化搜索即可。
AC代码
#include <cmath> #include <algorithm> #include <cstring> #include <utility> #include <string> #include <iostream> #include <map> #include <set> #include <vector> #include <queue> #include <stack> using namespace std; #pragma comment(linker, "/STACK:1024000000,1024000000") #define eps 1e-10 #define inf 0x3f3f3f3f #define PI pair<int, int> typedef long long LL; const int maxn = 20 + 2; int d[maxn][maxn][maxn][maxn], cake[maxn][maxn]; int n, m, k; int Count(int x, int y, int k, int h) { int cnt = 0; for(int i = x; i < x + k; ++i) for(int j = y; j < y + h; ++j) { cnt += cake[i][j]; if(cnt >= 2) return 2; } return cnt; } int dfs(int x, int y, int k, int h) { int &ans = d[x][y][k][h]; if(ans != -1) return ans; int cnt = Count(x, y, k, h); if(cnt == 1) return ans = 0; else if(!cnt) return ans = inf; ans = inf; //枚举列 for(int i = 1; i < h; ++i) { ans = min(ans, dfs(x, y, k, i)+dfs(x, y+i, k, h-i)+k); } //枚举行 for(int i = 1; i < k; ++i) { ans = min(ans, dfs(x, y, i, h)+dfs(x+i, y, k-i, h)+h); } return ans; } int main() { int kase = 1; while(scanf("%d%d%d", &n, &m, &k) == 3) { memset(d, -1, sizeof(d)); memset(cake, 0, sizeof(cake)); int x, y; for(int i = 0; i < k; ++i) { scanf("%d%d", &x, &y); cake[x][y] = 1; } printf("Case %d: %d\n", kase++, dfs(1, 1, n, m)); } return 0; } 如有不当之处欢迎指出！
