跳转至

CF598E

知识点

  • 动态规划
  • 记忆化搜索

题意简述

给定一个 \(n\times m\) 的矩阵,将 \(r\times c\) 的矩阵切成 \(r \times c'\)\(r\times (c - c')\) 的矩阵需要 \(r^2\) 的花费。

求切出大小和为 \(k\) 的矩阵所需最小花费。多组数据1

数据范围:\(1 \le T \le 40910\)\(1 \le n, m \le 30\)\(1 \le k \le \min(n\cdot m, 50)\)

解题思路

\(f(x, y, z)\) 表示要从 \(x\times y\) 的矩阵中切出大小和为 \(z\) 的矩阵所需最小花费。

我们可以枚举要将 \(x\times y\) 切成 \(x \times y'\)\(x\times (y - y')\),还是切成 \(x'\times y\)\((x - x')\times y\)

不难发现转移方程为 $$ f(x, y, z) = \min \begin{cases} x^2 + f(x, y', z') + f(x, y - y', z - z') \quad(y' \in [1, \left\lfloor\dfrac{y}{2}\right\rfloor], z' \in [0, z]) \\ y^2 + f(x', y, z') + f(x - x', y, z - z') \quad(x' \in [1, \left\lfloor\dfrac{x}{2}\right\rfloor], z' \in [0, z]) \end{cases} $$

答案即为 \(f(n, m, k)\)

代码实现

核心部分已用高亮标出。

Code
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <bits/stdc++.h>
#define LL long long

const int inf = 0x3f3f3f3f;
const int N = 30 + 5;
const int M = 30 + 5;
const int K = 50 + 5;

int n, m, k, f[N][M][K];

int F(int x, int y, int z) {
    if(f[x][y][z])
        return f[x][y][z];
    if(z == x * y || !z)
        return 0;
    int res = inf;
    for(int i = 1; i <= x - i; ++i)
        for(int j = 0; j <= z; ++j)
            res = std::min(res, y * y + F(i, y, j) + F(x - i, y, z - j));
    for(int i = 1; i <= y - i; ++i)
        for(int j = 0; j <= z; ++j)
            res = std::min(res, x * x + F(x, i, j) + F(x, y - i, z - j));
    return f[x][y][z] = res;
}

int32_t main() {
    int __tests;
    scanf("%d", &__tests);
    while(__tests--) {
        scanf("%d %d %d", &n, &m, &k);
        printf("%d\n", F(n, m, k));
    }
    return 0;
}

  1. 原题链接: E. Chocolate Bar