题解 | 乘积最大-牛客假日团队赛9A题

输入描述:

1. 由题中"可将它分成个部分"得出，这是区间划分类的题目。

2. 要求找出区间最大值，因为乘号放在任何一个位置都不一定是等效的结果，有子结构。

3. 要求最大值也就是间接性求最优子结构，子结构最优后的得出总体最优。符合无后效性。

题面题意分析后可以得出这是一道区间划分DP题。

1. 以加入的乘号数量作为划分阶段。

2. 用 表示原数字前 n 位中加入 k 个乘号所得表达式的最大值。

3. 预处理出表示原数字第 i 位到第 j 位组成的数字。

4. 

代码（无高精度）

#include<bits/stdc++.h>
using namespace std;

long long dp[45][45],num[45][45];
bool tong[45][45];
int n,k;
char ch[45];

inline void init()
{
    cin >> n >> k;
    cin >> ch;

    for(int i = 0;i < n;i++)
    {
        for(int j = 0;j < n;j++)
        {
            if(i <= j)
            {
                for(int k = i;k <= j;k++)
                {
                    num[i][j]*=10;
                    num[i][j]+=ch[k]-'0';
                }
            }
        }
    }
}

long long dfs(int n,int k)
{
    if(k == 0) return num[0][n-1];
    if(tong[n-1][k-1]) return dp[n-1][k-1];

    for(int i = k;i < n;i++)
        dp[n-1][k-1] = max(dp[n-1][k-1],dfs(i,k-1)*num[i][n-1]);

    tong[n-1][k-1] = true;

    return dp[n-1][k-1];
}

int main(int argc, char const *argv[])
{
    init();
    cout << dfs(n,k);
    getchar();getchar();getchar();
    return 0;
}