乘积最大
P1018 [NOIP2000 提高组] 乘积最大
我们直接先考虑 DP。
令 \(f[i][j]\) 表示前 \(i\) 个数，放置 \(j\) 个乘号的答案。
我们考虑转移最后一个乘号的位置，设最后一个乘号放在第 \(k\) 位和第 \(k+1\) 位之间，可以得到方程 \(f[i][j]=\max(f[k][j-1]\times num[k+1:i])\)，\(num[l:r]\) 表示数字串中，\([l,r]\) 这一段的数字串对应的数字。
由于 __int128 的最大值仅仅只有大约 \(1.7\times10^{38}\)，而答案最大是 \(9999999999999999999800000000000000000001\)（大概估计：\(40\) 个 \(9\)，然后对半是最大的，即 \(20\) 个 \(9\) 的平方，共 \(40\) 位）。所以我们考虑要用高精度了。
可是我们不一定要这么老实，因为答案仅仅多了几位，我们可以尝试用几个 __int128 进行模拟高精度。
我发现如果按照正常的压位，那么最低位需要处理两个 __int128 类型相乘除以压的位数，这样会溢出，不好处理。
我们可以不老实一些，低位压到 \(19\) 位（恰好是 unsigned long long 的数据规模，实际上比 long long 略大一点），高位不管位数（就是高位不需要按照 \(19\) 位进制，直接存储除了低位外的所有值）然后最大的乘积就是 \((10^{19}-1)^2\)，没有达到 __int128 的上限，乘法由于只有 \(4\) 位，很好实现，具体看代码。
还有需要注意的是 \(num[l:r]\)，为了优化复杂度，我们可以先用 \(O(n^2)\) 预处理，预处理时只需要写一个简单的高精乘10加数即可（可以线性预处理，但是需要实现减法）。
DP 的复杂度为 \(O(n^2k)\)。