乘积最大 题解

简化问题：

给原数字之前添加一个"1 *"，乘号不计入数量，对答案无影响。
例如："1231"可以变成"(1*)1231"。

---

表示状态

dp[i][j] = max num（最后一个乘号之前的最大乘积）

• i：此时在第i个数的前面添了一个乘号
• j：用了j个乘号

例1："(1*)12*31"：

• dp[2][1] = 12　（数位从0开始从左向右编号）

例2："(1*)1231"

• dp[3][2] = 12*3 = 36

---

找出答案

max dp[i][t] * cal_sec(i,n-1)
cal_sec(x,y)将数字串中[x,y]这个区间的字符串转化为数字

例如：设n=4,t=1.

此时为"(1*)1231"
则此时这种方案的乘积为dp[2][1] "31" = 12*31

---

转移方程

dp[i][j] = max dp[k][j-1] * cal_sec(k,i-1)

在前面的某一段乘积后面再续上一串数字，达到第i位，用了j个乘号。
前面的某一段乘积：枚举最后一个乘号在第k个数字之前，用了j-1个乘号。
要续的数字：从第k位到i-1位 = cal_sec(k,i-1)

---

边界条件

初始时用了0个乘号，但乘积为1。
例如："(1*)1231".
特判：如果输入的数字就是0，则直接返回0.

---

AC代码

#include <iostream>
#include <stdio.h>
#include <string.h>
#define MAX_N 45
#define MAX_K 35

using namespace std;
int n,t;
long long ans;
long long dp[MAX_N][MAX_K];
long long sec[MAX_N][MAX_N];
string s;

void read()
{
    cin>>n>>t>>s;
}

long long cal_sec(int x,int y)
{
    if(sec[x][y]!=-1) return sec[x][y];
    long long res=0;
    for(int i=x;i<=y;i++)
    {
        res=res*10+s[i]-'0';
    }
    return sec[x][y]=res;
}

void solve()
{
    memset(sec,-1,sizeof(sec));
    memset(dp,-1,sizeof(dp));
    dp[0][0]=1;
    for(int i=1;i<n;i++)
    {
        for(int j=1;j<=t && j<=i;j++)
        {
            for(int k=0;k<i;k++)
            {
                if(dp[k][j-1]!=-1)
                {
                    dp[i][j]=max(dp[i][j],dp[k][j-1]*cal_sec(k,i-1));
                }
            }
        }
    }
    ans=0;
    for(int i=0;i<n;i++)
    {
        if(dp[i][t]!=-1) ans=max(ans,dp[i][t]*cal_sec(i,n-1));
    }
}

void print()
{
    cout<<ans<<endl;
}

int main(){
    read();
    solve();
    print();
}