洛谷1018 乘积最大

原题链接

设\(f[i][j]\)表示在\([1, i]\)中放置\(j\)个乘号，且第\(i\)个数字后面放第\(j\)个乘号时所获得的最大乘积。$ace(1, i)表示将\(1 \sim i\)的数字变为一个数。
有状态转移方程：
\[f[i][j] = \max \{ f[i][j], \max \limits _{suc = j - 1} ^ {suc < i} \{ ace(suc + 1, i) \times f[suc][j - 1] \} \}\]
初始化\(f[i][1] = ace(1, i)\)，其余为空。
最后的答案就是\(\max \limits _{i = k} ^ {i < n} \{ ace(i + 1, n) \times f[i][k] \}\)
因为\(n\)可达到\(40\)，所以要用高精。

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 50;
const int K = 10;
struct bigint {
    int s[N << 3], l;
    void CL() { l = 0; memset(s, 0, sizeof(s)); }
    void pr()
    {
        printf("%d", s[l]);
        for (int i = l - 1; i; i--)
            printf("%d", s[i]);
    }
    bigint operator * (bigint &b)
    {
        bigint c;
        int i, j, k, x;
        c.CL();
        for (i = 1; i <= l; i++)
        {
            x = 0;
            for (j = 1; j <= b.l; j++)
            {
                x = x + s[i] * b.s[j] + c.s[k = i + j - 1];
                c.s[k] = x % 10;
                x /= 10;
            }
            if (x)
                c.s[i + b.l] = x;
        }
        for (c.l = l + b.l; !c.s[c.l] && c.l > 1; c.l--);
        return c;
    }
    bool operator < (const bigint &b) const
    {
        if (l ^ b.l)
            return l < b.l;
        for (int i = l; i; i--)
            if (s[i] ^ b.s[i])
                return s[i] < b.s[i];
        return false;
    }
};
bigint f[N][K], an;
int a[N], l;
inline void re_l()
{
    char c = getchar();
    for (; c < '0' || c > '9'; c = getchar());
    for (; c >= '0' && c <= '9'; c = getchar())
        a[++l] = c - '0';
}
inline bigint maxn(bigint x, bigint y) { return x < y ? y : x; }
bigint ace(int x, int y)
{
    bigint o;
    o.l = y - x + 1;
    for (int i = x; i <= y; i++)
        o.s[i - x + 1] = a[y - i + x];
    return o;
}
int main()
{
    int i, j, k, n, suc;
    scanf("%d%d", &n, &k);
    re_l();
    for (i = 1; i < n; i++)
    {
        f[i][1] = ace(1, i);
        for (j = 2; j <= k; j++)
            for (suc = j - 1; suc < i; suc++)
                if (f[suc][j - 1].l)
                    f[i][j] = maxn(f[i][j], ace(suc + 1, i) * f[suc][j - 1]);
        if (f[i][k].l)
            an = maxn(an, ace(i + 1, n) * f[i][k]);
    }
    an.pr();
    return 0;
}

洛谷1018 乘积最大

原文：https://www.cnblogs.com/Iowa-Battleship/p/10121555.html