首页 > 代码库 > wikioi 1017--乘积最大

wikioi 1017--乘积最大

2024-07-08 05:00:21   223人阅读

给定一个数串，以及K，求对这个数串K划分的乘积最大值。

DP思路：一开始肯定想到的是递归，假设在某两个字符间有一个乘号，那么乘积最大就是乘号两边的区间接着划分的乘积最大值。

于是状态空间表示如下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 }

 


联系
我们