记录编号	12799	评测结果	AAAAAAAAAA
题目名称	[NOIP 2000PJ]乘积最大	最终得分	100
用户昵称	yanzheng	是否通过	通过
代码语言	C++	运行时间	0.014 s
提交时间	2009-09-20 20:24:58	内存使用	0.29 MiB

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

ifstream fin("cjzd.in");
ofstream fout("cjzd.out");
string S;
long long N,K;
long long sum[MAX][MAX],F[MAX][MAX];
 
void init()
{
	int i,j;
	string t;
	fin >> N >> K >> S;
	K++;
	for (i=1;i<=N;i++)
	{
		for (j=i;j<=N;j++)
		{
			t=S.substr(i-1,j-i+1);
			sscanf(t.c_str(),"%d",&sum[i][j]);
		}
	}
}
 
inline long long max(long long a,long long b)
{
	return a>b?a:b;
}
 
void dynamic()
{
	int i,j,k;
	for (i=1;i<=N;i++)
		F[i][1]=sum[1][i];
	for (j=2;j<=K;j++)
	{
		for (i=1;i<=N;i++)
		{
			F[i][j]=0;
			for (k=1;k<=i-1;k++)
			{
				F[i][j]=max(F[i][j],F[k][j-1]*sum[k+1][i]);
			}
		}
	}
	fout << F[N][K];
}

int main()
{
	init();
	dynamic();
	return 0;
}