[SNCPC2024] 表达式矩阵

Luogu

IDLGP10692

Time1000ms

Memory512MB

DifficultyP4

搜索2024Special JudgeO2优化陕西省赛/邀请赛状压 DP

一个 $n \times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件： - 矩阵只包含 '1'，'+'，'*' 字符。 - 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。 - 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表达式求值后的值求和的结果。求所有 $n \times m$ 的合法表达式矩阵中，权值最小的那一个。如果有多个最小的答案，你可以给出任意一个。我们定义字符串 $s$ 是合法表达式如下： - 如果 $s = \overbrace{111\dots111}^{\text{至少一个 }1}$，则 $s$ 是合法表达式。 - 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ * $t$ 也是合法表达式。 - 如果 $s$ 和 $t$ 均为合法表达式，则 $s$ + $t$ 也是合法表达式。 ## Input 输入仅一行两个整数 $n, m$ ($3 \leq n, m \leq 9$)，由空格隔开，为矩阵的行数和列数。 ## Output 输出共 $n$ 行，每行 $m$ 个字符，其中第 $i$ 行的第 $j$ 个字符为 $a_{ij}$，为权值最小的矩阵。如果有多个最小的答案，你可以给出任意一个。 [samples] ## Note 对于样例，此时矩阵的权值为 $4488$，可以证明不存在权值更小的矩阵。

Samples

Input #1

4 4

Output #1

API Response (JSON)

{
  "problem": {
    "name": "[SNCPC2024] 表达式矩阵",
    "description": {
      "content": "一个 $n \\times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件： - 矩阵只包含 '1'，'+'，'*' 字符。 - 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。 - 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。 一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10692"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "一个 $n \\times m$ 的字符矩阵 $a_{ij}$，被称为合法的表达式矩阵，当且仅当其满足如下条件：\n\n- 矩阵只包含 '1'，'+'，'*' 字符。\n\n- 对于矩阵的每行从左向右组成的字符串，均为合法的表达式。\n\n- 对于矩阵的每列从上向下组成的字符串，均为合法的表达式。\n\n一个合法的表达式矩阵的权值定义为，每行从左向右组成的字符串和每列从上向下组成的字符串共 $n + m$ 个表达式...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments