AcWing 1026. 乘积最大
原题链接
简单
作者:
sy123
,
2021-03-06 16:53:53
,
所有人可见
,
阅读 322
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 45 , M = 10;
int n , k;
int w[N];
int num[N][N];
int f[N][M];
int main(){
char ch;
cin >> n >> k;
int i = 0;
while(cin >> ch)
{
w[++i] = ch - '0';
}
for(int i = 1 ; i <= n ; i++)
for(int j = i ; j <= n ;j++)
{
num[i][j]=num[i][j-1]*10+w[j];
}
for(int i = 1 ; i <= n ;i++)f[i][0] = num[1][i];
for(int i = 1 ; i <= n ;i++)
for(int j = 1 ; j <= k&&j<=i-1 ;j++)
for(int h = 2 ; h <= i ; h++)
f[i][j] = max(f[i][j] , f[h - 1][j - 1] * num[h][i]);
cout << f[n][k] << endl;
return 0;
}