最大k乘积问题
时间： 1ms 内存：64M
描述：
设I是一个n位十进制整数。如果将I划分为k段，则可得到k个整数。这k 个整数的乘积称为I的一个k乘积。试设计一个算法，对于给定的I和k，求出I的最大k乘积。
对于给定的I和k，计算I的最大k乘积。
输入：
输入数据的第1 行中有2个正整数n和k。正整数n是序列的长度；正整数k是分割的段数。
接下来的一行中是一个n位十进制整数。（n<=10）
输出：
只有一个输出数据，是计算出的最大k乘积。
示例输入：
2 1
15示例输出：
15提示：
参考答案（内存最优[1388]）：
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<sstream>
using namespace std;
int ans[100][100];
int f[100][100];
int main()
{
int n,k;
while(cin>>n>>k)
{
int t;
cin>>t;
stringstream ss;
ss<<t;
string s;
ss>>s;
// reverse(s.begin(),s.end());
// cout<<"s=="<<s<<endl;
int i,j;
for(i=1; i<=n; i++)
for(j=1; i+j<=n+1; j++)
{
ans[i][j]=(t%((int)pow(10,n-i+1))-t%((int)pow(10,n-i-j+1)))/pow(10,n-i-j+1);
// cout<<pow(10,n-i+2)<<" "<<pow(10,n-i-j+2)<<endl;
// cout<<"ans[i][j]=="<<ans[i][j]<<"i=="<<i<<"j=="<<j<<endl;
}
for(i=0; i<n; i++)
{
f[i+1][1]=t/(int)pow(10,n-i-1);
// cout<<"f[i+1]=="<<f[i+1][1]<<endl;
}
f[2][2]=(s[0]-'0')*(s[1]-'0');
// cout<<"f[2][2]=="<<f[2][2]<<endl;
for(i=3; i<=n; i++)
{
f[i][i]=f[i-1][i-1]*(s[i-1]-'0');
// cout<<"f[i][i]=="<<f[i][i]<<"i=="<<i<<endl;
}
for(j=2; j<=k; j++)
for(i=j; i<=n; i++)
{
int m;
int max=-1000000;
for(m=1; m<=i+1-j; m++)
{
// cout<<"f[i-m][j-1]=="<<i-m<<" "<<j-1<<" "<<f[i-m][j-1]<<endl;
// cout<<"ans[i-m+1][m]=="<<i-m+1<<" "<<m<<" "<<ans[j+1-m][m]<<endl;
if(f[i-m][j-1]*ans[i-m+1][m]>max)
max=f[i-m][j-1]*ans[i-m+1][m];
// cout<<"max=="<<max<<endl;
}
f[i][j]=max;
// cout<<"f[i][j]=="<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
cout<<f[n][k]<<endl;
}
return 0;
}参考答案（时间最优[16]）：
#include<iostream>
#include<string>
#include<algorithm>
#include<cmath>
#include<sstream>
using namespace std;
int ans[100][100];
int f[100][100];
int main()
{
int n,k;
while(cin>>n>>k)
{
int t;
cin>>t;
stringstream ss;
ss<<t;
string s;
ss>>s;
// reverse(s.begin(),s.end());
// cout<<"s=="<<s<<endl;
int i,j;
for(i=1; i<=n; i++)
for(j=1; i+j<=n+1; j++)
{
ans[i][j]=(t%((int)pow(10,n-i+1))-t%((int)pow(10,n-i-j+1)))/pow(10,n-i-j+1);
// cout<<pow(10,n-i+2)<<" "<<pow(10,n-i-j+2)<<endl;
// cout<<"ans[i][j]=="<<ans[i][j]<<"i=="<<i<<"j=="<<j<<endl;
}
for(i=0; i<n; i++)
{
f[i+1][1]=t/(int)pow(10,n-i-1);
// cout<<"f[i+1]=="<<f[i+1][1]<<endl;
}
f[2][2]=(s[0]-'0')*(s[1]-'0');
// cout<<"f[2][2]=="<<f[2][2]<<endl;
for(i=3; i<=n; i++)
{
f[i][i]=f[i-1][i-1]*(s[i-1]-'0');
// cout<<"f[i][i]=="<<f[i][i]<<"i=="<<i<<endl;
}
for(j=2; j<=k; j++)
for(i=j; i<=n; i++)
{
int m;
int max=-1000000;
for(m=1; m<=i+1-j; m++)
{
// cout<<"f[i-m][j-1]=="<<i-m<<" "<<j-1<<" "<<f[i-m][j-1]<<endl;
// cout<<"ans[i-m+1][m]=="<<i-m+1<<" "<<m<<" "<<ans[j+1-m][m]<<endl;
if(f[i-m][j-1]*ans[i-m+1][m]>max)
max=f[i-m][j-1]*ans[i-m+1][m];
// cout<<"max=="<<max<<endl;
}
f[i][j]=max;
// cout<<"f[i][j]=="<<i<<" "<<j<<" "<<f[i][j]<<endl;
}
cout<<f[n][k]<<endl;
}
return 0;
}题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。