暑假集训day1 水题乘法最大

题目大意：有一个长度为N的字符串，要求用K个乘号将其分成K+1个部分，求各个部分相乘的最大值

输入：第一行输入N和K，第二行输入一个长度为N的字符串

算法分析

  1.  这个题只是一个简单的dp（甚至连区间dp都不是）

  2.  dp[i][j]表示前i个数字里面用了j个乘号，而枚举的状态k表示前k个数字用了j-1个乘号，然后用dp[k][j-1]去和后面的数字相乘

  3.  由2可知我们需要一个数组sum[i][j]表示从i到j的数字（也就这和平时的题不一样了）：

          想一下如果说后面3个数字为123那么要乘的便是123，而我们平时的算法前缀和或者直接读取数据并不能表示出从1这个位置到3这个位置表示的一百二十三

          所以我们用sum数组提前处理好

          `for(int i = 1;i <= n;++i)

		for(int j = i;j <= n;++j)

			sum[i][j] = sum[i][j-1]*10 + b[j];`

  `

   4.sum数组处理好就是一个简单的dp了，下面是代码



#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n,m,b[maxn],sum[50][50],dp[50][50];

char a[maxn];

int main(){

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

	for(int i = 1;i <= n;++i){

		scanf(" %c",&a[i]);

		b[i] = a[i]-'0';

	}

	for(int i = 1;i <= n;++i)

		for(int j = i;j <= n;++j)

			sum[i][j] = sum[i][j-1]*10+b[j];

	dp[0][0] = 1;

	for(int i = 1;i <= n;++i)dp[i][0] = sum[1][i];

	for(int i = 1;i <= n;++i)

		for(int j = 1;j <= i;++j){

			if(dp[i][i-1] == 0)dp[i][i-1] = 1;

			dp[i][i-1] *= b[j];

		}

	dp[1][0] = b[1];

	for(int i = 2;i <= n;++i)

		for(int j = 1;j < i && j <= m;++j)

			for(int k = j;k < i;++k)

				dp[i][j] = max(dp[i][j],dp[k][j-1]*sum[k+1][i]);

	printf("\n%d\n",dp[n][m]);

	return 0;

}

巴特西

暑假集训day1 水题乘法最大

最新文章

热门文章

巴特西

暑假集训day1 水题 乘法最大

最新文章

热门文章

暑假集训day1 水题乘法最大