题解 | #[NOIP2000]乘积最大#
[NOIP2000]乘积最大
https://ac.nowcoder.com/acm/problem/16751
思路
这道题用Py写很方便,因为懒得想dp所以就直接跑暴力过了。
代码
RES=0
maxn=55
dp=[[0 for i in range(maxn)] for j in range(maxn)]
mp=[[0 for i in range(maxn)] for j in range(maxn)]
def dfs(pos,sc,cnt):
global RES
if sc<mp[pos][cnt]:
return
mp[pos][cnt]=sc
if cnt==k :
if RES<sc*dp[pos+1][n-1]:
RES=sc*dp[pos+1][n-1]
return
for i in range(pos+1,n):
dfs(i,sc*dp[pos+1][i],cnt+1)
return
n,k=map(int,input().split(' '))
str=input()
for i in range(0,n):
for j in range(i,n):
#print(i,j,"!!")
dp[i][j]=int(str[i:j+1])
for i in range(0,n):
dfs(i,dp[0][i],1)
print(RES)