$\text{蒟蒻在DP之路上求索着}$

题面:luogu P1018 乘积最大

分析

又是一道字符串相关的DP,其实我做这道题也是为了练习高精度乘法.题目中给了k个乘号,那么我们来考虑它们的位置.因为乘号位置的不同直接导致了结果的不同,所以我们设$f[i][j]$表示把$i$个乘号放到前$j$个数字之间,在前$j$个数字的范围内能得到的最大解.在考虑子问题的时候就好好考虑子问题,而不是同时挂念着整体.

那么假设我们现在已经放了$i-1$个乘号,手中拿着第$i$个乘号,我们应该怎么转移呢?我们枚举这个乘号的位置,因为可以放置乘号个数的上界是$min(k,j-1)$,所以我们可能有多个位置可以放.如果我们放在第$p$个数字和第$p+1$个数字之间,那么就把第$1$到$p$个和第$p+1$到$j$个数字分开了,我么只需要用$f[i-1][p]\times num[p+1][j]$来更新答案就可以了.其中$num[p+1][j]$表示我们提取出来的数字.

DP代码:

for (int i = 1; i <= n; ++i)
    for (int j = i; j; --j)
        f[0][i].c[++f[0][i].length] = a[j];
for (int i = 2; i <= n; ++i)
    for (int j = 1; j <= min(k, i - 1); ++j)
        for (int p = j; p < i; ++p)
            f[j][i] = max(f[j][i], super_mul(f[j - 1][p], p + 1, i));

当然了,我写这个题还是为了学高精度乘法,在上面的$max()$和$super_mul()$函数中.

高精度乘法代码:

struct node {
    int length;//记录长度
    int c[100];//记录答案(倒序)
}f[10][100];

inline node super_mul(node a1, int l, int r) {
    node ret, b;//暂存器
    memset(ret.c, 0, sizeof(ret.c));
    memset(b.c, 0, sizeof(b.c));
    b.length = r - l + 1;
    for (int i = r; i >= l; --i)//储存乘数
        b.c[r - i + 1] = a[i];
    int la = a1.length, lb = b.length;
    for (int i = 1; i <= la; ++i)//由于没有压位不担心爆炸所以直接乘
        for (int j = 1; j <= lb; ++j)
            ret.c[i + j - 1] += a1.c[i] * b.c[j];
    int lr = la + lb - 1;
    for (int i = 1; i <= lr; ++i) {//乘完了再进位
        ret.c[i + 1] += ret.c[i] / 10;
        ret.c[i] %= 10;
    }
    if (ret.c[lr + 1]) lr++;
    ret.length = lr;
    return ret;
}

inline node max(node x, node y) {//比较两个长整数的大小
    int lx = x.length, ly = y.length;
    if (lx > ly) return x;
    if (lx < ly) return y;
    for (int i = lx; i; --i) {
        if(x.c[i] > y.c[i]) return x;
        if(x.c[i] < y.c[i]) return y;
    }
    return x;
}

——Gensokyo