AcWing 1026. 乘积最大
原题链接
简单
作者:
我要出去乱说
,
2021-02-15 20:28:57
,
所有人可见
,
阅读 662
#include <iostream>
using namespace std;
typedef long long LL;
int n, k;
string num;
LL dfs(int u, int s, LL v, LL p)
{
if (u == n)
{
if (s == k + 1) return p; //合法方案才返回结果
return -1;
}
else
{
v = v * 10 + num[u] - '0'; //更新当前枚举的数
//在第u位后面不加乘号的情况和在第u位后面加乘号的情况
return max(dfs(u + 1, s, v, p), dfs(u + 1, s + 1, 0, p * v));
}
}
int main()
{
cin >> n >> k >> num;
//四个参数分别为:枚举到第几位,当前有几个数(乘号个数+1),当前枚举的数,乘积是多少
cout << dfs(0, 0, 0, 1) << endl;
return 0;
}
主函数里,dfs中第二个参数 对于当前有几个数 不应该是乘号个数+1吗 所以最后当s==k+1的时候才会退出
对对对,感谢提醒,已修改。