P1018 乘积最大

题目描述

今年是国际数学联盟确定的“20002000――世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：

设有一个长度为的数字串，要求选手使用个乘号将它分成个部分，找出一种分法，使得这个部分的乘积能够为最大。

同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：

有一个数字串：， 当时会有以下两种分法：

1、
2、

这时，符合题目要求的结果是:

现在，请你帮助你的好朋友设计一个程序，求得正确的答案。

输入格式

程序的输入共有两行：

第一行共有个自然数

第二行是一个长度为的数字串。

输出格式

结果显示在屏幕上，相对于输入，应输出所求得的最大乘积（一个自然数）。

输入输出样例

输入

4 2
1231

输出

62

说明/提示

NOIp2000提高组第二题

解题思路一

这题可以使用深度优先遍历做，根据左边数字的划分位置，递归求右侧划分次可以得到的最大乘积，然后与左边数字相乘，寻找最大值。
例如可以先将 划分为 和 ,再计算 可以经过划分得到的最大值，这里可以看出最大值为 .

这题还有一个问题就是数值范围太大，如果不使用高精度计算，只能通过60%。
高精度计算可以参考另一篇博文：https://www.jianshu.com/p/85e3220b011c。

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<iomanip>

using namespace std;
const int power = 4; //压位
const int base = 10000;
const int LEN = 105;

class UNum {
public:
    int a[LEN + 1];

    //清空数字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    UNum() {
        clear();
    }

    UNum(const char *s, int len) {
        this->clear();
        //a[0]保存数字长度，此时一个int保存一个4位长度的数字
        a[0] = (len + power - 1) / power;
        for (int t = 1; t <= a[0]; ++t) {
            for (int i = max(len - t * power, 0); i < min(len, len - t * power + power); ++i) {
                a[t] = 10 * a[t] + (s[i] - '0');
            }
        }
    }

    friend bool operator<(const UNum &p, const UNum &q) {
        if (p.a[0] < q.a[0]) return true;
        if (p.a[0] > q.a[0]) return false;
        for (int i = p.a[0]; i > 0; --i) {
            if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];
        }
        return false;
    }

    friend UNum operator*(const UNum &p, const UNum &q) {
        UNum c;
        c.a[0] = p.a[0] + q.a[0] - 1;
        for (int i = 1; i <= p.a[0]; ++i)
            for (int j = 1; j <= q.a[0]; ++j) {
                c.a[i + j - 1] += p.a[i] * q.a[j];
                c.a[i + j] += c.a[i + j - 1] / base;
                c.a[i + j - 1] %= base;
            }
        if (c.a[c.a[0] + 1]) ++c.a[0];
        return c;
    }

    friend ostream &operator<<(ostream &os, const UNum &num) {
        int i = num.a[0];
        cout << num.a[i--];
        for (; i > 0; --i) cout << setw(power) << setfill('0') << num.a[i];
        cout << '\n';
        return os;
    }
};


class Key {
public:
    int start = 0;
    int end = 0;
    int k = 0;

    friend ostream &operator<<(ostream &o, const Key &key) {
        o << '(' << key.start << ',' << key.end << ',' << key.k << ')';
        return o;
    }

    Key(int s, int e, int k) : start(s), end(e), k(k) {
    }

    bool operator==(const Key &key) const {
        if (this == &key)
            return true;
        return this->start == key.start && this->end == key.end && this->k == key.k;
    }
};


namespace std {
    template<>
    struct hash<Key> {
        size_t operator()(const Key &s) const noexcept {
            return hash<int>()(s.start) + hash<int>()(s.end) + hash<int>()(s.k);
        }
    };
}


UNum dfs(const char *list, int start, int end, int k, unordered_map<Key, UNum> &rem) {
    if (k == 0) {
        UNum m(list + start, end - start + 1);
        return m;
    }
    if (start == end || (end - start) < k)
        return UNum();
    if (rem.find(Key(start, end, k)) != rem.end()) {
        return rem[Key(start, end, k)];
    }
    UNum m;
    for (int i = start; i < end; ++i) {
        UNum left(list + start, i - start + 1);
        if (rem.find(Key(i + 1, end, k - 1)) == rem.end()) {
            rem.insert(make_pair(Key(i + 1, end, k - 1), dfs(list, i + 1, end, k - 1, rem)));
        }
        UNum right = rem[Key(i + 1, end, k - 1)];
        m = max(m, left * right);
    }
    return m;
}

int main() {
    int N = 0, K = 0;
    cin >> N >> K;
    
    //这里直接开N大小，有可能通不过，不知道为啥，本地能通过
    //看来在最开始直接开最大最好 emmm
    char *numbers = new char[N + 2];
    cin >> numbers;
    unordered_map<Key, UNum> rem;
    UNum res = dfs(numbers, 0, N - 1, K, rem);
    cout << res;
    delete[] numbers;
    return 0;
}

解题思路二

可以利用动态规划,表示前 位添加了 个乘号时的最优解, 表示原字符串。
状态转移方程：
参考链接：https://www.luogu.com.cn/blog/14378/solution-p1018

#include<iostream>
#include<algorithm>
#include<unordered_map>
#include<iomanip>

using namespace std;
const int power = 4; //压位
const int base = 10000;
const int LEN = 105;

class UNum {
public:
    int a[LEN + 1];

    //清空数字
    void clear() {
        for (int i = 0; i <= LEN; ++i) a[i] = 0;
    }

    UNum() {
        clear();
    }

    UNum(const char *s, int len) {
        this->clear();
        //a[0]保存数字长度，此时一个int保存一个4位长度的数字
        a[0] = (len + power - 1) / power;
        for (int t = 1; t <= a[0]; ++t) {
            for (int i = max(len - t * power, 0); i < min(len, len - t * power + power); ++i) {
                a[t] = 10 * a[t] + (s[i] - '0');
            }
        }
    }

    UNum &operator=(const UNum &num) {
        if (this == &num) return *this;
        this->clear();
        for (int i = 0; i <= num.a[0]; ++i) this->a[i] = num.a[i];
        return *this;
    }

    friend bool operator<(const UNum &p, const UNum &q) {
        if (p.a[0] < q.a[0]) return true;
        if (p.a[0] > q.a[0]) return false;
        for (int i = p.a[0]; i > 0; --i) {
            if (p.a[i] != q.a[i]) return p.a[i] < q.a[i];
        }
        return false;
    }

    friend UNum operator*(const UNum &p, const UNum &q) {
        UNum c;
        c.a[0] = p.a[0] + q.a[0] - 1;
        for (int i = 1; i <= p.a[0]; ++i)
            for (int j = 1; j <= q.a[0]; ++j) {
                c.a[i + j - 1] += p.a[i] * q.a[j];
                c.a[i + j] += c.a[i + j - 1] / base;
                c.a[i + j - 1] %= base;
            }
        if (c.a[c.a[0] + 1]) ++c.a[0];
        return c;
    }

    friend ostream &operator<<(ostream &os, const UNum &num) {
        int i = num.a[0];
        cout << num.a[i--];
        for (; i > 0; --i) cout << setw(power) << setfill('0') << num.a[i];
        cout << '\n';
        return os;
    }
};

char s[LEN];
UNum f[LEN][LEN];

int main() {
    int N = 0, K = 0;
    cin >> N >> K >> s;
    for (int i = 0; i <= N; ++i) {
        f[0][i] = UNum(s, i+1);
    }

    for (int i = 1; i <= K; i++)
        for (int j = 1; j <= N; j++) {
            for (int v = j; v >= i; v--) {
                f[i][j] = max(f[i][j], f[i - 1][v - 1] * UNum(s + v, j - v + 1));
            }
        }
    cout << f[K][N-1];
    return 0;
}