0
已解决
高级守护
#include<bits/stdc++.h>
using namespace std;
long long f[101][101];
int m,len,a[101];
char n[101];
long long cut(int x,int y){
int s=0,k=1;
for(int i=x;i<=y;i++){
s+=a[i]*k;
k=k*10;
}
return s;
}
int main()
{
int t;
cin>>t;
for(int l=1;l<=t;l++)
{
cin>>n;cin>>m;
len=strlen(n);
for(int i=1;i<=len;i++)
a[i]=n[i-1]-'0';
memset(f,0,sizeof(f));
for(int i=1;i<=len;i++)
f[i][0]=cut(1,i);
for(int i=2;i<=len;i++)
for(int j=1;j<=min(i-1,m-1);j++)
for(int k=j;k<=i-1;k++)
f[i][j]=max(f[i][j],f[k][j-1]*cut(k+1,i));
cout<<f[len][m-1]<<endl;
}
return 0;
}
0
已采纳
高级守护
创建二维数组 f[][] ,用 f[i][j] 表示前 i 位数包含 j 个乘号所能达到的最大乘积
- 将 i 从 2 到 n 枚举，表示分割为前i位数字
- 对每一次分割再次将 a 从 1 到 min(i-1,k) 枚举，表示前 i 位中含有 a 个乘号
- 将 b 从 a 到 i - 1 进行一次枚举，表示前 i 位中含有 a 个乘号，且最后一个乘号的位置在 b 处。那么当最后一个乘号在 b 处时最大值为前 b 位中含有 a - 1 个乘号的最大值乘上 b 处之后的数字
- 因此得出了状态转移方程 f[i][a] = max(f[i][a] , f[b][a-1] * cut(b + 1,i))
——（cut(b + 1,i) 表示 b + 1 到 i 位数字） - //核心代码如下
- for(int j=1;j<=lenth;j++)
g[j]=n[j-1]-'0';
for(int j=1;j<=lenth;j++)
f[j][0]=cut(1,j);
for(int j=2;j<=lenth;j++)
for(int a=1;a<=min(j-1,m-1);a++)
for(int b=a;b<=j-1;b++)
f[j][a]=max(f[j][a],f[b][a-1]*cut(b+1,j));
cout<<f[lenth][m-1]<<endl; - 前面还有一段把字符转换数字的小函数，就由你来完成了,祝你最后ac
- 望采纳，谢谢
0
初级天翼
正如他们所说
0
高级天翼
可采纳楼上。
0
高级天翼
要用二维数组
0
高级守护
- 前面还有一段把字符转换数字的小函数，就由你来完成了,祝你最后ac
