AcWing 1026. 乘积最大
原题链接
简单
作者:
shenbc
,
2021-04-09 22:19:08
,
所有人可见
,
阅读 332
#include<iostream>
#include<cstring>
using namespace std;
const int N=15;
int n,k;
string s;
long long path[N],p;
long long ans;
//last为子串起始点,pos为子串当前点,cnt为当前乘号数
void dfs(int last,int pos,int cnt){
//cout<<last<<" "<<pos<<" "<<cnt<<endl;
if(pos>=n)return;
if(cnt==k){
path[p++]=stoi(s.substr(last));
//for(int i=0;i<p;i++)cout<<path[i]<<" ";
//cout<<endl;
long long res=1;
for(int i=0;i<p;i++){
res*=path[i];
}
ans=max(res,ans);
//cout<<"res: "<<res<<endl;
p--;
return;
}
//path保存这串数字中已经确定(插入/不插入)乘号的部分
path[p++]=stoll(s.substr(last,pos-last+1));//注意 long long 很坑
dfs(pos+1,pos+1,cnt+1);
p--;//cout<<"p: "<<p<<endl;
dfs(last,pos+1,cnt);
return;
}
int main(){
cin>>n>>k;
cin>>s;
dfs(0,0,0);//s[0]~s[0],已经加了几个乘号
cout<<ans<<endl;
return 0;
}