P1018 [NOIP2000 提高组] 乘积最大

题目

题目链接

题解

状态定义：dp[i][j]表示前i个数分成j段（即需要j+1个*）的最大乘积。 状态转移：dp[i][j] = max(dp[k-1][j-1]*a[k][i], dp[i][j])，表示在第k-1和第k个数之间加上一个*得到的最大值，其中前k-1个数采用的是dp值，即被分为了j-1段后的最大值，而后面的数（从k到i）则视为一整个数，与前面的dp值相乘。遍历全部k的位置，取最大值即为 dp[i][j]。

首先，暴力是不行的，暴力枚举每个*的位置，O(40^6)=O((2^12)*(10^6))=O(4,096,000,000)。

再者，由于要保存和计算的数最高为40位，因此还需要采用高精度。（之前写的高精度，有空重新整理一下）

整体思路就是先写出来非高精度版，再将其中的乘、加改成高精度的函数即可。

高精度函数：

1. max：计算两个高精度数的较大者，并返回string类型的高精度数。
2. add：计算一个高精度数和一个int类型数的和，因为用不到两个高精度数相加，所以就写了这一个。
3. mul：重载成两个函数了。第一个是计算两个高精度数的乘积，返回string类型的高精度数；第二个是计算一个高精度数与10相乘的结果。

另：如果在提交时出现RE，或者测试我给出的样例时出现了奇怪错误，要么是数组开小了，要么是高精度乘法最后位数的处理出现了问题。（经验之谈）

代码

未采用高精度的60%代码：

#include
using namespace std;
const int N = 50, M = 10;

int n, m;
long long dp[N][M], a[N][N];
string num;

int main()
{
	cin >> n >> m;
	cin >> num;
	
	for (int i = 0;i