最大k乘积问题.txt

最大K乘积问题。这个一个可以实现的代码。大家看看

#include<fstream>
#include<iostream>
#include<string>
using namespace std;
#define MAX 1000

/*设I(s,t)是I的由从s位开始的t位数字组成的十进制数。
f(i,j)表示I(0,i)的最大j乘积，则f(i,j)具有最优子结构性质。

计算f(i,j)的动态规划递归式如下：
f(i,j)=max{f(k,j-1)*I(k,i-k)}   1≤k<i

  */


int f[MAX][MAX],ka[MAX][MAX];
string str("15654");


int conv(int i, int j)	//conv计算机I(s,t)的值。
{
	string str1=str.substr(i,j);
	cout<<str1.c_str()<<endl;
	return atoi(str1.c_str());
}



void solve(int n, int m)
{
	int i,j,k;
	int temp,maxt,tk;
	for(i=1;i<=n;i++)
		f[i][1]=conv(0,i);
	for(j=2;j<=m;j++)
		for(i=j;i<=n;i++)
			for(k=1,temp=0;k<i;k++)
			{
				maxt=f[k][j-1]*conv(k,i-k);
				if(temp<maxt)
				{
					temp=maxt;tk=k;
				}
				f[i][j]=temp;
				ka[i][j]=tk;
			}
}





void out(int n,int m)
{
	ofstream cout1("kmu1.out");
	cout1<<f[n][m]<<endl;
	for(int i=m, k=n; i>=1&&k>0; k=ka[k][i],i--)
		cout1<<"f["<<k<<"]["<<i<<"]="<<f[k][i]<<endl;
}


int main()
{
	int n,m;
	ifstream cin1("kmu1.in");
	cin1>>n>>m;
	cout<<n<<"   "<<m<<endl;
	/*
	if((n<m)||(n==0))
	{
		cout<<0<<endl;
		return 0;
	}*/
	cin1>>str;
/*
	if(n!=str.size())
	{
		cout<<0<<endl;
		return 0;
	}*/
	cout<<str<<endl;
	solve(n,m);
	out(n,m);
	return 0;
}