[NOIP 2000 提高组] 乘积最大

Luogu
IDLGP1018
Time1000ms
Memory128MB
DifficultyP4
动态规划 DP高精度2000NOIP 提高组线性 DP
今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度为 $N$ 的数字串,要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分,找出一种分法,使得这 $K+1$ 个部分的乘积能够为最大。 同时,为了帮助选手能够正确理解题意,主持人还举了如下的一个例子: 有一个数字串:$312$,当 $N=3,K=1$ 时会有以下两种分法: 1. $3 \times 12=36$ 2. $31 \times 2=62$ 这时,符合题目要求的结果是:$31 \times 2 = 62$。 现在,请你帮助你的好朋友 XZ 设计一个程序,求得正确的答案。 ## Input 程序的输入共有两行: 第一行共有 $2$ 个自然数 $N,K$。 第二行是一个长度为 $N$ 的数字串。 ## Output 结果显示在屏幕上,相对于输入,应输出所求得的最大乘积(一个自然数)。 [samples] ## Background NOIP2000 提高组 T2 ## Note **数据范围与约定** 对于 $60\%$ 的测试数据满足 $6≤N≤20$。 对于所有测试数据,$6≤N≤40,1≤K≤6$。
Samples
Input #1
4 2
1231
Output #1
62
API Response (JSON)
{
  "problem": {
    "name": "[NOIP 2000 提高组] 乘积最大",
    "description": {
      "content": "今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目: 设有一个长度为 $N$ 的数字串,要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分,找出一种分法,使得这 $K+1$ 个部分的乘",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 131072
    },
    "difficulty": {
      "LuoguStyle": "P4"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP1018"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "今年是国际数学联盟确定的“2000——世界数学年”,又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛,组织了一场别开生面的数学智力竞赛的活动,你的一个好朋友 XZ 也有幸得以参加。活动中,主持人给所有参加活动的选手出了这样一道题目:\n\n设有一个长度为 $N$ 的数字串,要求选手使用 $K$ 个乘号将它分成 $K+1$ 个部分,找出一种分法,使得这 $K+1$ 个部分的乘积...",
      "is_translate": false,
      "language": "English"
    }
  ]
}
Full JSON Raw Segments