AcWing 3718. 插入乘号(dfs+模拟)
原题链接
简单
#include<iostream>
#define int long long
using namespace std;
int n, k, ans=-1, flag[15];
string s;
void dfs(int cnt){
// 当已经达到分割次数k时
if(cnt==k){
int res=1, temp=0, idx=-1; // 初始化
for(int i=0;i<n;i++){
// 如果第一个字符就被标记为分割点,则退出循环
if(flag[0]==1) break;
// 如果当前位置被标记为分割点
if(flag[i]){
idx=i; // 记录分割点索引
res*=temp, temp=0, temp=temp*10+s[i]-'0';// 计算分割点之前的数字乘积
}
else temp=temp*10+s[i]-'0'; // 如果当前位置不是分割点,则继续计算数字
}
// 如果没有找到分割点,直接返回
if(idx == -1) return;
// 计算后面的数字并且更新temp以及res
temp=0;
for(int i=idx;i<n;i++) temp=temp*10+s[i]-'0';
res*=temp;
ans=max(ans,res); // 更新最大乘积ans
return ;
}
// 尝试所有可能的分割点
for(int i=cnt;i<n;i++){
if(!flag[i]){
flag[i]=1; // 标记
dfs(cnt+1); // 递归
flag[i]=0; // 回溯
}
}
}
signed main(){
cin>>n>>k>>s;
dfs(0);
cout<<ans<<endl;
return 0;
}