Wikioi - 1017 乘积最大

1017.c

/* Wikioi - Problem 1017 Maxmul. by Abreto. */
#include <stdio.h>
#define MAXL	(50)
#define MAXK	(10)

typedef long long int lint;

int N = 0, K = 0;
char a[MAXL] = {0};
lint g[MAXL][MAXL] = {{0}};
lint f[MAXL][MAXK] = {{0}};

lint
dp(int i, int j)
{
	int k = 0;
	lint max = 0, t = 0;
	lint *ans = &(f[i][j]);
	
	if( *ans )
	{
		return *ans;
	}
	
	if( 0 == j )
	{
		return (*ans = g[0][i]);
	}
	
	for(k = i-1;k >= j-1;--k)
	{
		t = dp(k,j-1) * g[k+1][i];
		if(max < t)
			max = t;
	}
	
	return (*ans = max);
}

int
main(void)
{
	int i = 0, j = 0, k = 0;
	
	scanf("%d %d\n", &N, &K);
	for(i = 0;i < N;++i)
	{
		scanf("%c", a+i);
		a[i] -= '0';
	}
	
	/* init array of g */
	for(j = N-1;j >= 0;--j)
	{
		int c = 1;
		for(i = j;i >= 0;--i)
		{
			g[i][j] = g[i+1][j] + (lint)(a[i]) * c;
			c *= 10;
		}
	}
	/* end 'init'. */
	
	printf("%lld\n", dp(N-1,K));
	return 0;
}