AcWing 1026. 乘积最大(大暴力)
原题链接
简单
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int n,k,ans;
string exp;
bool vis[20];//标记数字是否出现过
vector<int>num;//存放分割的数字
int number(int l,int r)//求区间[l,r]的数字
{
int s=0;
for(int i=l;i<=r;i++)
i==l?s=(exp[i]-'0'):s=s*10+(exp[i]-'0');
return s;
}
void dfs(int pos,int cnt)
{
if(cnt==k)
{
int y=number(pos,n-1);//求出分割k次以后,第k+1个数的大小
num.push_back(y);//放入分割的数字中
int tmp=1;
for(int i=0;i<num.size();i++)//求乘积
tmp*=num[i];
// cout<<num[i]<<" ";
// cout<<endl;
ans=max(ans,tmp);//更新最大值
num.pop_back();
return;
}
for(int i=0;i<n-1;i++)//枚举分割位置
{
if(!vis[i]&&pos<=i)//如果分割位置未出现过,向下搜索
{
int x=number(pos,i);
num.push_back(x);
vis[i]=true;
dfs(i+1,cnt+1);
vis[i]=false;
num.pop_back();
}
}
}
int main()
{
cin>>n>>k;
cin>>exp;
ans=0;
dfs(0,0);
cout<<ans<<endl;
return 0;
}
厉害!