题目
今年是国际数学联盟确定的“2000——世界数学年”，又恰逢我国著名数学家华罗庚先生诞辰 90 周年。在华罗庚先生的家乡江苏金坛，组织了一场别开生面的数学智力竞赛的活动，你的一个好朋友 XZ 也有幸得以参加。活动中，主持人给所有参加活动的选手出了这样一道题目：
设有一个长度为 的数字串，要求选手使用 个乘号将它分成 个部分，找出一种分法，使得这 个部分的乘积能够为最大。
同时，为了帮助选手能够正确理解题意，主持人还举了如下的一个例子：
有一个数字串：312，当n=3，k=1时会有以下两种分法：312=36；312=62；
这时，符合题目要求的结果是：31*2=62。
现在，请你帮助你的好朋友 XZ 设计一个程序，求得正确的答案。
输入
第一行共有2个自然数N，K（6≤N≤40，1≤K≤6）
第二行是一个长度为N的数字串。
输出
输出所求得的最大乘积（一个自然数）。
样例
4 2
1231
62
代码
点击查看代码
#include"bits/stdc++.h"
using namespace std;
int m,len;
string n;
string f[250][250],a[250][250];
string dp[250][250];
//dp[i][j]表示前i位拆成j段
//string的a.compare(b)函数比大小，在一些编译器上会返回“1”（a>b）“-1”（a<b）“0”（a=b），但是有一些编译器会返回正数、0、负数（就应为这个我调了一下午加半上午，恼了）
int comp(string x,string y)
{
if(x.length()>y.length())return 1;
else if(x.length()<y.length())return -1;
else return x.compare(y);
}
//数据范围太大了，要打高精，这里完全是string的高精乘和加，因为我觉得转来转去太麻烦了干脆直接到最后都用string输出
string add(string str1,string str2)
{
string str;
int len1=str1.length();
int len2=str2.length();
if(len1<len2)
{
for(int i=1;i<=len2-len1;i++)
str1="0"+str1;
}
else
{
for(int i=1;i<=len1-len2;i++)
str2="0"+str2;
}
len1=str1.length();
int cf=0;
int temp=0;
for(int i=len1-1;i>=0;i--)
{
temp=str1[i]-'0'+str2[i]-'0'+cf;
cf=temp/10;
temp%=10;
str=char(temp+'0')+str;
}
if(cf!=0) str=char(cf+'0')+str;
return str;
}
string cheng(string str1,string str2)
{
string str;
int len1=str1.length();
int len2=str2.length();
string tempstr;
for(int i=len2-1;i>=0;i--)
{
tempstr="";
int temp=str2[i]-'0';
int t=0;
int cf=0;
if(temp!=0)
{
for(int j=1;j<=len2-1-i;j++)
tempstr+="0";
for(int j=len1-1;j>=0;j--)
{
t=(temp*(str1[j]-'0')+cf)%10;
cf=(temp*(str1[j]-'0')+cf)/10;
tempstr=char(t+'0')+tempstr;
}
if(cf!=0) tempstr=char(cf+'0')+tempstr;
}
str=add(str,tempstr);
}
str.erase(0,str.find_first_not_of('0'));
return str;
}
int main()
{
cin >>len>>m>>n;
//预处理：把数字拆开
for (int i=1;i<=249;i++)
{
for (int j=1;j<=249; j++)
{
dp[i][j]="0";
}
}
//m表示乘号个数，m+1表示分成几段，和dp的照应
m+=1;
for(int i=0;i<len;i++)
{
for(int j=i;j<len;j++)
{
f[i+1][j+1]=n.substr(i,j-i+1);
}
}
//初始化
for(int i=0;i<=len;i++)
{
for(int j=0;j<=len;j++)
{
dp[i][j]="0";
}
}
dp[0][0]="1";//dp为string类型，所以赋值为字符'1'
for(int i=1;i<=len;i++)
{
int ki=min(i,m);
for(int j=1;j<=ki;j++)
{
for(int k=1;k<=i;k++)
{
if(comp(cheng(dp[k-1][j-1],f[k][i]),dp[i][j])>0)//一定要写>0,下面会写为啥
{
dp[i][j]=cheng(dp[k-1][j-1],f[k][i]);
}
}
}
}
cout <<dp[len][m];
return 0;
}
写这个题解的原因
主要是因为昨天下午写出来以后，没A，23-PeppaEvenPig就给我改，也没过，偶然间发现在v
scode上和oi上跑出来的结果不一样，在vscode上A了，所以就一直调，然后再acwing上跑，结果输出还和oi上不一样，就很无语，最后经过铸（这字念tao，别管为啥）哥的不懈努力，发现compare的问题，就离谱了，然后改了之后就A了，浪费我半天的时间，恼了。（手动愤怒）