UVA1629 切蛋糕 Cake slicing

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

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

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

代码:

  1. #include <iostream>
  2. #include <cstdio>
  3. #include <cstring>
  4. #include <algorithm>
  5. using namespace std;
  6. const int N = 30;
  7. int dp[N][N][N][N];
  8. int p[N][N];
  9. int cs;
  10. int pnum(int lx, int ly, int rx, int ry)
  11. {
  12. return p[rx][ry] - p[lx - 1][ry] - p[rx][ly - 1] + p[lx - 1][ly - 1];
  13. }
  14. int DP(int lx, int ly, int rx, int ry)
  15. {
  16. if (pnum(lx, ly, rx, ry) == 0) return 0x3f3f3f3f;
  17. if (pnum(lx, ly, rx, ry) == 1) return 0;
  18. int &d = dp[lx][ly][rx][ry];
  19. if (d != 0x3f3f3f3f) return d;
  20. for (int i = lx; i < rx; i ++)
  21. d = min(d, DP(lx, ly, i, ry) + DP(i + 1, ly, rx, ry) + ry - ly + 1);
  22. for (int i = ly; i < ry; i ++)
  23. d = min(d, DP(lx, ly, rx, i) + DP(lx, i + 1, rx, ry) + rx - lx + 1);
  24. return d;
  25. }
  26. int main()
  27. {
  28. int n, m, k;
  29. while(scanf("%d%d%d", &n, &m, &k) != EOF && n && m)
  30. {
  31. memset(p, 0, sizeof p);
  32. for (int i = 0; i < k; i ++)
  33. {
  34. int a, b;
  35. scanf("%d%d", &a, &b);
  36. p[a][b] = 1;
  37. }
  38. for (int i = 1; i <= n; i ++)
  39. for (int j = 1; j <= m; j ++)
  40. p[i][j] += p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1];
  41. memset(dp, 0x3f, sizeof dp);
  42. printf("Case %d: %d\n", ++cs, DP(1, 1, n, m));
  43. }
  44. return 0;
  45. }
添加新评论