python/TangDou/KaoShi/玻璃球乘积.cpp

#include <bits/stdc++.h>

using namespace std;
int n;
const int N = 110;
const int INF = 0x3f3f3f3f;
int st[N];
int a[N];
int res = -INF;
/*
测试用例：
5　

答案：
6　
*/
void dfs(int u, int r, int last) {
    //递归出口
    if (r == 0) {
        if (u >= 2) {
            //　输出每个拆分办法
            // for (int i = 0; i < u - 1; i++) cout << a[i] << " * ";
            // cout << a[u - 1];

            //计算累乘积
            int t = 1;
            for (int i = 0; i < u; i++) t *= a[i];
            // cout << " = " << t << endl;

            //猴子选大王
            res = max(res, t);
        }
        return;
    }

    for (int i = last + 1; i <= r; i++) {
        if (!st[i]) {
            st[i] = true;
            a[u] = i;

            dfs(u + 1, r - i, i);

            a[u] = 0;
            st[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs(0, n, 0);
    printf("%d\n", res);
    return 0;
}