[蓝桥杯2018决赛]最大乘积

链接： http://oj.ecustacm.cn/problem.php?id=1397

把 1~9 这9个数字分成两组，中间插入乘号，
有的时候，它们的乘积也只包含1~9这9个数字，而且每个数字只出现1次。
比如：
984672 * 351 = 345619872
98751 * 3462 = 341875962
9 * 87146325 = 784316925
...
符合这种规律的算式还有很多，请你计算在所有这些算式中，乘积最大是多少？

答案：839542176

方法：穷举.......(这里我用了递归枚举)，当然也可以用多for个嵌套来实现

#include <iostream>
#include <vector> 
#include <cmath>
#define ll long long

using namespace std;

ll data;// 用来保存每一次穷举后，每个数字只出现一次的一串数字 
int mem[10]; // 用来记录数字是否被添加到此次的数据中 
ll ans;// 保存结果 


// 判断是否满足条件 
bool isNotRepeat(ll res) {
    ll box[10];
    for (int i = 0; i < 10; i++) {
        box[i] = 0;
    }
    while(res > 0) {
        box[res%10]++;
        res /= 10;
    }
    for (int i = 1; i < 10; i++) {
        if (box[i] == 0) {// 说明有重复的数字 
            return false; 
        }
    }
    return true;
} 

// 把遍历后的一串没有重复的数字串，通过递归去拿取满足条件的最大值 
ll getMaxValue(ll d, int index) {
    if (index > 8) return 0;
    
    // 截取的位置往后移动一位 
    ll nextRes = getMaxValue(d, index+1);
    
    // 截取前一段 
    ll pre = d / (ll)(pow(10, 9-index));
    // 截取后一段 
    ll last = d % (ll)(pow(10, 9-index));
    
    ll res = pre*last;
    // 判断结果是否满足条件 
    if (isNotRepeat(res)) {
        return res > nextRes ? res : nextRes;
    }
    return nextRes;
}


// 递归遍历 
void dfs(ll d, int len) {
    
    // 如果数据长度为9时，结束递归 
     if (len >= 10) {
         // 去拿取这一串数据被切分后满足条件乘积的最大值
         ll res = getMaxValue(d, 1);
         if (res > ans) ans = res;
         return;
     }
     
    
    for (int i = 1; i <= 9; i++) {
        // 通过mem数组来实现去重，然后回溯一下 
        if (mem[i] == 0) {
            mem[i] = 1;
            dfs(d *10 + i, len+1);
            mem[i] = 0;
        }
        
    }
}

int main() {
    // 初始化 
    for (int i = 0; i < 10; i++)
        mem[i] = 0;
    ans = data = 0;
    
    
    dfs(data, 1); 
    cout << ans << endl;
    
    
    return 0;
}