题目链接:点击查看
题目大意:给出一个长度为
n
n
n 的仅由数字
1
?
9
1-9
1?9 组成的字符串,问恰好添加
m
m
m 个加号后,等式的最小值是多少
题目分析:不需要考虑前导
0
0
0,而且仅有加号,不难想到很经典的
d
p
[
i
]
[
j
]
dp[i][j]
dp[i][j],代表前
i
i
i 个位置,划分了
j
j
j 段后的最小答案,转移方程也是经典的
d
p
[
i
]
[
j
]
=
m
i
n
0
≤
k
<
i
(
d
p
[
k
]
[
j
?
1
]
)
dp[i][j]=min_{0\le k < i}(dp[k][j-1])
dp[i][j]=min0≤k<i?(dp[k][j?1]),时间复杂度是
O
(
n
3
)
O(n^3)
O(n3),空间复杂度
O
(
n
2
)
O(n^2)
O(n2)
然后本题需要关注的是,需要用到高精度加法,所以空间复杂度如果正常去想的话,也是
O
(
n
3
)
O(n^3)
O(n3) 的
如何优化呢?有个需要想到的思维点是,因为有
m
m
m 个加号,所以最终需要分成
m
+
1
m+1
m+1 段,我们令每一段的长度尽量相等一定是最优的
如此一来时间复杂度可以优化到
O
(
n
2
)
O(n^2)
O(n2),而空间复杂度也可以优化为
O
(
n
?
m
?
n
m
=
n
2
)
O(n * m * \frac{n}{m}=n^2)
O(n?m?mn?=n2)
用
p
y
t
h
o
n
python
python 写起来比较简单
代码:
n,m=map(int,input().split())
m=m+1
s=" "+input()
dp=[[-1 for j in range(1010)] for i in range(1010)]
len=n//m
dp[0][0]=0
for i in range(1,n+1):
for j in range(1,min(i,m)+1):
for k in range(i-len-2,i-len+3):
if k>=j-1 and k<i and dp[k][j-1]!=-1:
if dp[i][j]==-1 or dp[i][j]>dp[k][j-1]+int(s[k+1:i+1]):
dp[i][j]=dp[k][j-1]+int(s[k+1:i+1])
print(dp[n][m])
|