AcWing 1026. 乘积最大
原题链接
简单
作者:
cange
,
2021-04-16 09:31:31
,
所有人可见
,
阅读 318
#include<bits/stdc++.h>
using namespace std;
int N,K;
int maxnum=0;
int cnt=0;
string nums; //数字串
int str[20]; //乘法插入的下标
int vis[20];
int getNum(){
stringstream ss;
for(int i=0;i<nums.size();i++){
if(str[i+1]==1) ss<<nums[i]<<" ";
else ss<<nums[i];
}
int tmp,sum=1;
while(ss>>tmp) sum=sum*tmp;
return sum;
}
void dfs(int index){
if(cnt==K){
maxnum=max(maxnum,getNum());
return;
}
for(int i=index;i<=N-1;i++){
if(!vis[i]){
vis[i]=1;
str[i]=1;
cnt++;
dfs(index+1);
str[i]=0;
cnt--;
vis[i]=0;
}
}
}
int main(){
cin>>N>>K;
cin>>nums;
dfs(1);
cout<<maxnum;
}