給定一個數(shù)串，以及K，求對這個數(shù)串K劃分的乘積最大值。

DP思路：一開始肯定想到的是遞歸，假設(shè)在某兩個字符間有一個乘號，那么乘積最大就是乘號兩邊的區(qū)間接著劃分的乘積最大值。

于是狀態(tài)空間表示如下dp[i][k]表示從0~i之間有K個乘號的乘積最大值，

dp[i][k] = max(dp[j][k-1]*num[j+1][i])(k<=j<=i-1)

1 #include <iostream> 2 #include <queue> 3 #include <climits> 4 #include <algorithm> 5 #include <memory.h> 6 #include <stdio.h> 7 #include <ostream> 8 #include <vector> 9 #include <list> 10 #include <cmath> 11 #include <string> 12 using namespace std; 13 14 int num[50][50]; 15 int dp[50][10]; 16 int main() 17 { 18 int N,K; 19 string s; 20 cin>>N>>K; 21 cin>>s; 22 int i,j; 23 for(i = 0 ; i < N ; ++i) 24 { 25 int tmp = 0; 26 for(j = i ; j < N ; ++j) 27 { 28 tmp = tmp*10+s[j]-'0'; 29 num[i][j] = tmp; 30 } 31 } 32 memset(dp,0,sizeof(dp)); 33 for(j = 0; j < N ; ++j) 34 { 35 dp[j][0] = num[0][j]; 36 } 37 for(j = 0; j < N ; ++j) 38 { 39 int k,t; 40 for(k = 1;k <= K; ++k) 41 { 42 for(t = 0; t < j;++t) 43 { 44 dp[j][k] = max(dp[t][k-1]*num[t+1][j],dp[j][k]); 45 } 46 } 47 } 48 cout<<dp[N-1][K]<<endl; 49 return 0; 50 }

?

轉(zhuǎn)載于:https://www.cnblogs.com/cane/p/3787628.html

總結(jié)

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

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