【NOIP2000】【vijos1347】乘积最大

problem

solution

codes

//f[i][j]:前i位数包含j个乘号时能获得的最大值
//转移，枚举每个乘号的位置即可，O(n^3)可过。
#include<iostream>
#include<algorithm>
#include<string>
using namespace std;
typedef long long LL;
int n, m;
LL f[110][110];
string s;
LL mid(int l, int r){
    LL t = 0;
    for(int i = l; i <= r; i++)
        t = t*10+s[i-1]-'0';//第i位在s[i-1];
    return t;
}
int main(){
    cin>>n>>m>>s;
    for(int i = 1; i <= n; i++)f[i][0] = mid(1,i);//边界条件，没有乘号
    for(int i = 1; i <= n; i++) //枚举前i位数
        for(int j = 1; j <= min(m,i-1); j++)//枚举每个乘号(即子状态)
            for(int k = j; k < i; k++)//枚举该乘号的位置,乘号放后面(保证第j个乘号时, 前j-1个乘号的最优状态已经算出来了）
                f[i][j] = max(f[i][j], f[k][j-1]*mid(k+1,i));
    cout<<f[n][m]<<"\n";
    return 0;
}
  

 

  
1
  
2
  
3
  
4
  
5
  
6
  
7
  
8
  
9
  
10
  
11
  
12
  
13
  
14
  
15
  
16
  
17
  
18
  
19
  
20
  
21
  
22
  
23
  
24
  
25
  
26
 

文章来源: gwj1314.blog.csdn.net，作者：小哈里，版权归原作者所有，如需转载，请联系作者。

原文链接：gwj1314.blog.csdn.net/article/details/80516442