题目链接：乘积最大
这道题显然是道区间dp。
难度不是很大。
思路也很清晰。
我们设计一个三维状态。
ans[l][r][k]
这里表示在闭区间[l,r]上操作k次的最大值。
操作就是加乘号。
转移也很好转移，写一个双循环，外层循环断点，内层循环两段的操作次数。
下面放代码：
#include<bits/stdc++.h>
#ifdef WIN32
#define LL "%I64d"
#else
#define LL "%lld"
#endif
using namespace std;
long long ans[45][45][8];
long long dp(char* num,int l,int r,int k){
if(ans[l][r][k]>=0){ //1
return ans[l][r][k];
}
if(k==0){ //2
long long x=0;
for(int i=l;i<=r;i++){
x=x*10+num[i]-'0';
}
ans[l][r][k]=x;
return x;
}
for(int i=l;i<r;i++){ //3
for(int j=0;j<=k-1&&j<=(i-l)&&(k-1-j)<=(r-i-1);j++){ //4
ans[l][r][k]=max(ans[l][r][k],dp(num,l,i,j)*dp(num,i+1,r,k-1-j)); //5
}
}
return ans[l][r][k];
}
int main(){
int n,k;
scanf("%d%d",&n,&k);
char num[n];
memset(ans,-1,sizeof(ans));
char c;
scanf("%c",&c);
scanf("%s",num);
printf(LL,dp(num,0,n-1,k));
return 0;
}讲五处：
1处：如果该值已经计算过，那么直接返回，记忆化搜索。
2处：如果操作数为0，说明该区间所有的数字都视为一个数，那么直接计算该数，并返回。
3处：循环断点。
4处：循环操作次数，有两个限制条件，第一个是不得超过当前操作次数；第二是左右两边分配的操作次数不得超过他们的区间长度减1，因为如果只有3个数，那最多只能加两个乘号，不能更多。
5处：两边计算结果成起来取最大值。