caioj 1067动态规划入门（一维一边推5：乘积最大(高精度版））

因为这里涉及到乘号的个数，那么我们可以用f[i][j]表示前i个位乘号为j个时的最大乘积

那么相比上一题就是多了一层枚举多少个乘号的循环，可以得出

f[i][r] = max(f[j - 1][r - 1], num(j, i));

num(j, i)表示第j位到第i位的数，j < i

然后注意要用高精度来计算。

#include<cstdio>

#include<algorithm>

#include<cstring>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

const int MAXN = 112;

struct node

{

	int len, s[MAXN];

	node() { len = 0; memset(s, 0, sizeof(s)); }

};

int n, k, a[MAXN];

node f[MAXN][10], sum[MAXN][MAXN];

node cut(int x, int y)

{

	node ret;

	for(int i = y; i >= x; i--)

		ret.s[++ret.len] = a[i];

	return ret;

}

node cheng(node a, node b)

{

	node ret;

	REP(i, 1, a.len + 1)

		REP(j, 1, b.len + 1)

		{

			ret.s[i + j - 1] += a.s[i] * b.s[j];

			ret.s[i + j] += ret.s[i + j - 1] / 10;

			ret.s[i + j - 1] %= 10;

		}

	int& i = ret.len = a.len + b.len - 1;

	while(ret.s[i+1] > 0)

	{

		i++;

		ret.s[i + 1] += ret.s[i] / 10;

		ret.s[i] %= 10;

	}

	while(!ret.s[i] && i > 1) i--;

	return ret;

}

node max_node(node a, node b)

{

	if(a.len > b.len) return a;

	else if(a.len < b.len) return b;

	else

	{

		for(int i = a.len; i >= 1; i--)

		{

			if(a.s[i] > b.s[i]) return a;

			else if(a.s[i] < b.s[i]) return b;

		}

	}

	return a;

}

int main()

{

	scanf("%d%d", &n, &k);

	REP(i, 1, n + 1) scanf("%1d", &a[i]), f[i][0] = cut(1, i);

	REP(i, 1, n + 1)

		REP(j, i, n + 1)

			sum[i][j] = cut(i, j);

	REP(r, 1, k + 1)  //乘号的循环在外面

		REP(i, 1, n + 1)

			for(int j = i; j > 1; j--) //这里大于1,边界要注意一下

				f[i][r] = max_node(f[i][r], cheng(f[j - 1][r - 1], sum[j][i]));

	node t = f[n][k];

	for(int i = t.len; i >= 1; i--) printf("%d", t.s[i]);

	puts("");

	return 0;

}

巴特西

caioj 1067动态规划入门（一维一边推5：乘积最大(高精度版））

最新文章

热门文章

巴特西

caioj 1067动态规划入门（一维一边推5： 乘积最大(高精度版））

最新文章

热门文章

caioj 1067动态规划入门（一维一边推5：乘积最大(高精度版））