AcWing 1026. 乘积最大
原题链接
简单
作者:
哈基咪
,
2020-08-17 17:44:30
,
所有人可见
,
阅读 939
#include<iostream>
#include<cstring>
using namespace std;
int n,k;
string num;
const int N=50;
int a[N];
int sum(int leftindex, int rightindex)
{
int sum=0;
int n;
for(int i=leftindex-1;i<=rightindex-1;i++)
{
n=num[i]-'0';
sum=sum*10+n;
}
return sum;
}
int dfs(int l, int r , int k)
{
if(k==0) return sum(l,r);
else if(r-l>=k&&k>0)
{
int res_max=0;
for(int i=l;i<r;i++)
{
int r1=sum(l,i);
int r2=dfs(i+1,r,k-1);
int res=r1*r2;
if(res>res_max)
{
res_max=res;
}
}
return res_max;
}
else return 0;
}
// int dfs(int l, int r, int k)
// {
// // 没有乘号插入,直接返回数字
// if(k == 0)
// {
// return sum(l, r);
// }
// else if(r-l>=k && k>0)
// {
// int mmax = 0;
// for(int i=l; i<r; i++)
// {
// // 左边表示的数字
// int r1 = sum(l, i);
// // 在右边插入k-1个乘号
// int r2 = dfs(i+1, r, k-1);
// int res = r1 * r2;
// if(res > mmax)
// {
// mmax = res;
// }
// }
// return mmax;
// }
// else
// {
// return 0;
// }
// }
int main()
{
cin>>n>>k;
cin>>num;
cout<<dfs(1,n,k)<<endl;
return 0;
}
tqltql