鏈接：https://ac.nowcoder.com/acm/contest/1071/A
來源：牛客網(wǎng)

時間限制：C/C++ 1秒，其他語言2秒
空間限制：C/C++ 262144K，其他語言524288K
64bit IO Format: %lld
題目描述
今年是國際數(shù)學(xué)聯(lián)盟確定的“2000——世界數(shù)學(xué)年”，又恰逢我國著名數(shù)學(xué)家華羅庚先生誕辰90周年。在華羅庚先生的家鄉(xiāng)江蘇金壇，組織了一場別開生面的數(shù)學(xué)智力競賽的活動，你的一個好朋友XZ也有幸得以參加。活動中，主持人給所有參加活動的選手出了這樣一道題目：
設(shè)有一個長度為N的數(shù)字串，要求選手使用K個乘號將它分成K+1個部分，找出一種分法，使得這K+1個部分的乘積能夠為最大。
同時，為了幫助選手能夠正確理解題意，主持人還舉了如下的一個例子：
有一個數(shù)字串：312， 當(dāng)N=3，K=1時會有以下兩種分法：

3*12=36

312=62
這時，符合題目要求的結(jié)果是：312=62
現(xiàn)在，請你幫助你的好朋友XZ設(shè)計一個程序，求得正確的答案。
輸入描述:
第一行共有2個自然數(shù)N，K（6 ≤ N ≤ 40，1 ≤ K ≤ 6）
第二行是一個長度為N的數(shù)字串。
輸出描述:
輸出所求得的最大乘積（一個自然數(shù)）。
示例1
輸入
復(fù)制

4 2 1231

輸出
復(fù)制

62

/*
當(dāng)時團隊賽時，感覺要大數(shù)計算就為了省事就用python寫的，
現(xiàn)在補一份C++代碼。
字符串s下標(biāo)從1開始，
dp[i][j]:表示 s[i]前 放j個 乘號，
那么有狀態(tài)轉(zhuǎn)移方程：

dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k+1][i]) j<= k < i，（ k>=j: j-1個乘號至少有j位 ）

*/

#include <bits/stdc++.h>using namespace std; typedef long long LL; char s[50]; LL num[50][50],dp[50][10]; void init(int n) {for(int i = 1; i <= n; i++){for(int j = i; j <= n; j++){num[i][j] = num[i][j-1] * 10 + (s[j]-'0');}} } int main() {int n,k;scanf("%d%d%s",&n,&k,s+1);init(n);for(int i = 1; i <= n; i++){dp[i][0] = num[1][i];for(int j = 1; j <= n; j++){for(int k = j; k < i; k++){dp[i][j] = max(dp[i][j],dp[k][j-1]*num[k+1][i]);}}}printf("%lld\n",dp[n][k]);return 0; }

用python只要爆搜就好：

vis = [False for x in range(n)] mp = [] ans = 0 def dfs(st,n,m,cnt,res):global ansif(n-st-1 < m-cnt):returnif(cnt == m):tm = resres *= mp[st][n-1]if res > ans:ans = resres = tmreturnfor i in range(st,n):if(vis[i]==False):vis[i] = True#print(mp[st][i])dfs(i+1,n,m,cnt+1,res*mp[st][i])vis[i] = False n,m = map(int,input().split()) s = input() tmp = 0 for i in range(n):my_list = []tmp = 0for j in range(n):if j < i:my_list.insert(j,0)continuetmp = tmp * 10 + int(s[j])my_list.insert(j,tmp)mp.insert(i,my_list) #print(mp) dfs(0,n,m,0,1) print(ans)

總結(jié)

以上是生活随笔為你收集整理的乘积最大(dp)的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。