最大k乘积问题

最大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;
}

题目和答案均来自于互联网,仅供参考,如有问题请联系管理员修改或删除。

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注