蓝桥杯算法训练VIP-乘积最大

题目

题目链接

题解

动态规划。

整体思路： dp[i][j]表示用i个乘号，对前j个数进行操作能得到的最大值；（看完dp数组如何定义后，可以尝试自己实现） num[i][j]表示第i个数到第j个数构成的十进制数的值； 转移方程：dp[i][j] = max(dp[i][j], dp[i-1][k-1]*num[k][j])，其中k是在枚举乘号的位置，k = i+1 ~ j 初始条件：dp[0][i] = num[1][i], dp[1][1] = 1

思考过程（以下单纯是为了记录自己的思考过程，读者自行选择忽略与否）：

最开始想到了其他的两种定义dp数组的方式：

1. dp[i][j]表示用i个乘号，第j个位置为最后一个乘号能得到的最大值；
2. dp[i][j][k]表示用i个乘号，第j个位置为最后一个乘号，前k个数能得到的最大值；

第一种只让最后一个乘号位于第j个位置上，显然会少很多情况，比如有可能正确答案是xxx * xx * xxx这样分割，但是此转移方程只能求出xxxxxxx * x剩下两个乘号随便放的情况下构成数的最大值，显然这不包含正解。（其中x为数字，*为乘号）

第二种为了解决第一种出现的问题，我多加了一维，后两维分别控制最后一个乘号的位置和最后一个数的位置，这样确实没问题，但我在写循环的时候发现要写四层循环，其中两层几乎一样，仔细一看才发现原来根本不需要第二维，因此我就将第二维去掉了，就有了正确的定义方式。（这其中的思考过程比较复杂，就不叙述了）

代码

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

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

int main()
{
	cin>>n>>m>>s;
	s = '.'+s;
	
	for(int i = 1;i