A40807. 最大乘积
填空题
困难
知识点
题目描述
最大乘积
题目描述
把 1~9 这9个数字分成两组，中间插入乘号，
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
…
符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？
答案提交
注意，需要提交的是一个整数，表示那个最大的积，不要填写任何多余的内容。
参考答案
#include <iostream>
#include <cstring>
using namespace std;
const int N = 10;
int a[N], st[N], s[N], ans;
bool judge(int n) // 判断 1~9 是否都出现了一次
{
while(n)
{
s[n % 10] ++;
n /= 10;
}
for (int i = 1; i < 10; i ++)
{
if(s[i] != 1) return false;
}
return true;
}
int divide(int l, int r) // 合并成一个数
{
int t = 0;
for (int i = l; i <= r; i ++)
{
t = t * 10 + a[i];
}
return t;
}
void dfs(int u)
{
if(u == 10)
{
for (int i = 1; i <= 8; i ++) // 分离成两个数字
{
int x = divide(1, i);
int y = divide(i + 1, 9);
if(judge(x * y)) ans = max(ans, x * y);
memset(s, 0, sizeof s); // 重置计数数组！！
}
return;
}
for (int i = 1; i <= 9; i ++)
{
if(!st[i])
{
a[u] = i;
st[i] = true;
dfs(u + 1);
st[i] = false;
}
}
}
int main()
{
dfs(1);
cout << ans <<endl;
return 0;
}答案解析
答案：839542176
上一题
下一题