pypy3 解法, 执行用时: 1960ms, 内存消耗: 35496K, 提交时间: 2022-06-02 21:10:39

INF = 10**1001
dp = [[INF] * 1010 for __ in range(1010)]
n, m = map(eval, input().split())
dp[0][0] = 0
m += 1
s = input()
s = '0' + s
lst = n // m + 2
for i in range(1, n + 1):
    for k in range(max(0, i - lst), i):
        for j in range(1 , m + 1):
            dp[i][j] = min(dp[i][j], dp[k][j - 1] + int(s[k + 1: i + 1]))
print(dp[n][m])

Python3 解法, 执行用时: 3198ms, 内存消耗: 23796K, 提交时间: 2022-10-06 16:46:22

inf = 10**1001
dp = [[inf for i in range(1010)] for j in range(1010)]
n,m = map(eval,input().split())
dp[0][0] = 0
m += 1
s = '0' + input()
l = n // m + 2
for i in range(1,n + 1):
    for k in range(max(0,i - l),i):
        for j in range(1,m + 1):
            dp[i][j] = min(dp[i][j],dp[k][j - 1] + int(s[k + 1:i + 1]))
print(dp[n][m])