乘积最大

由于题目给定的是m，需要分解成m+1部分的乘积，不难想到乘号刚好是m个，那么该题就转化成了m个乘号的插入方式。 

最优子结构分析：     

设数字字符串为a1a2…an        

m=1 时，一个乘号可以插在a1a2…an中的n-1个位置，这样就得到n-1种乘积：                        

a1*a2…an,   a1a2*a3…an, …, a1a2…a n-1*an           

此时的最大值= max { a1*a2…an, a1a2*a3…an, …, a1a2…a n-1*an }        

m=2时，两个乘号可以插在a1a2…an中n-1个位置的任两个地方，这样总共会产生 

个乘积。把这些乘积分个类，便于观察规律。 

Case1: a1a2 …*a n-1*an , a1a2 …*a n-2 a n-1*an , a1*a2 …a n-3 a n-2 a n-1 *  an ,   

  因后一个乘号位置不变，要使这些乘积最大，就要找出在前n-1个数中插入一个乘号的最大值。引入符号F(n-1,1)表示在前n-1个数中插入一个乘号的最大值,则  Case1的最大值为F(n-1, 1) * an

Case2: a1a2 …*a n-2*a n-1 an , a1a2 …*a n-3 a n-2* a n-1 an , a1*a2 …a n-3 a n-2 * a n-1 an ,     

因后一个乘号位置不变，要使这些乘积最大，就要找出在前n-2个数中插入一个乘号的最大值。设符号F(n-2)(1)为在前n-2个数中插入一个乘号的最大值,则 Case2的最大值为F(n-2,1） * a n-1 an 

同理，Case3的最大值为F(n-3,1) * a n-2 a n-1 an  …… Case n-2的最大值为F(2,1) * a3…an 

把一段数字串转化为一个整数： 

int get(int i,int j) { //将i~j这一段数字转化为一个整数 
    int ret=0;
    for(int k=i;k<=j;k++) {
        ret=ret*10+s[k]-'0';
    }
    return ret;
}

状态转移方程推导： 

下面以n=9, m=4, s=‘321044105’为例，说明计算过程。              

我们引入符号f(i,j)表示从a1~ai中插入j个乘号取得的最大值，g[i][j]表示从ai~aj的子串的数值。则上式可表示为：    

F(9,4) = max{f(8,3)*g[9][9], f(7,3)*g[8][9], f(6,3)*g[7][9], f(5,3)*g[6][9], f(4,3)*g[5][9]}    

F(8,3) = max{f(7,2)*g[8][8], f(6,2)*g[7][8], f(5,2)*g[6][8], f(4,2)*g[5][8],f(3,2)*g[4][8]}    

F(7,3) = max{f(6,2)*g[7][7], f(5,2)*g[6][7], f(4,2)*g[5][7], f(3,2)*g[4][7]}    

…………    

上面的分析已经看出问题的最优子结构、重复子问题性质。 

 定义状态：dp[i][j]表示从a1~aj中插入i个乘号取得的最大值 

dp[i][j] = max{ dp(i-1, k)*get(k+1, j) }  (1<=i<=m, i+1<=j<=n, i<=k<j )

i的取值范围为：乘号个数

j的取值范围为：乘号数i加1 ~ 数字串总个数

k的取值范围为：乘号个数~右边界j减去1

上式的边界条件是什么？

dp[0][i] = get(1, i)  (1<=i<=n)

我们要求的问题的最优解是dp[m][n]  

#include <bits/stdc++.h>
using namespace std;
long long n,k,dp[45][45],m;
char a[45];
long long num(long long x,long long y)
{
    long long sum=0;
    for(long long i=x;i<=y;i++)
    {
        sum=sum*10+a[i]-'0';
    }
    return sum;
 } 
int main()
{
    scanf("%lld%lld",&m,&n);
    scanf("%s",a+1);
    for(int i=1;i<=m;i++)
    {
        dp[0][i]=num(1,i);
    }
    for(long long i=1;i<=n;i++)
    {
        for(long long j=i+1;j<=m;j++)
        {
            for(long long k=i;k<j;k++)
            {
                dp[i][j]=max(dp[i-1][k]*num(k+1,j),dp[i][j]);
            }
        }
    }
    printf("%lld\n",dp[n][m]);
}