暴力不行(原因:若暴力枚举,时间复杂度为 O(40^6)=O(4,096,000,000)会TLE),所以选择dp。
状态定义: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]。
此外,还需要使用高精度