(DP) – 乘积最大 TJPUACM

1.概述:

原题感觉不是很难,但是一开始很难想到。而且实现起来也会有些需要想到的问题。我觉得这道题对于有些利用DP算法的题目的理解具有很大的帮助。比如Floyd算法的理解,可以看看我的另一篇文章哦。

2.题目的意思:

首先N个字符组成的序列,插入K个乘号,要求求出K+1段的乘积的最大。

3.比如1231要插入2个乘号,12之间可以插入1个乘号,最大的也就是1*2=2。现在123之间可以插入1、2个乘号。求前i个字符每一次插入k个乘号的时候,我可以分为前j个字符的最大成绩*j+1(j<=i-1)到组成的数字的最大值,然后一直搜索下去,从前j个字符不能插入k-1个乘号未知。考虑到,每次搜索都会有重复的计算,所以需要用一个数组保存。已知6<=N<=40,1<=K<=6。所以定义数组dp[41][7](从1开始)。所以就有dp[i][k]=max { dp[i][j] , num(str,j,k-1)) }。其中num(std::string &s,int b,int e)表示是字符串s的[b,e]所组成的字符串,dp[i][k]表示str前i的字符串插入k个乘号的最大值

4.代码(已AC):

#include  "stdio.h"
#include <string>
#include <algorithm>
#include <iostream>
using namespace std;
void remove_0(string &s)
{
	if (s.back() != '0')
	{
		reverse(s.begin(), s.end());//如果不需要去掉0 那么直接返回
	}
	else
	{
		int n;
                //去掉不需要的0
		for (n = s.size() - 1; n>0; --n)
		{
			if (s[n] == '0' && s[n - 1] != '0')
				break;
		}
		if (n == 0)
		{
			s = "0";
		}
		else {
			s = s.substr(0, n);
			reverse(s.begin(), s.end());
		}
	}
}
string plus1(string s, string s1)
{
	//for big plus
	if (s.size() == 0 || s1.size() == 0)
		return "0";
	string res(s.size() + s1.size(), '0');
	reverse(s.begin(), s.end());
	reverse(s1.begin(), s1.end());
	for (int i = 0; i<s.size(); ++i)
	{
		int add = 0;//乘法进位 
		int pl = 0;
		int j;
		for (j = 0; j<s1.size(); ++j)
		{
			int mul = (s[i] - '0')*(s1[j] - '0') + pl;
			pl = mul / 10;
			int aa = mul % 10 + (res[i + j] - '0') + add;
			add = aa / 10;
			res[i + j] = aa % 10 + '0';
		}
		res[i + j] = res[i + j] + pl+add;//最后的多余一项的乘法和加法需要进位
	}
	remove_0(res);
	return res;
}
string num(int b, int e, string &s)
{
	//获取s的数值
	return s.substr(b, e - b + 1);
}
const string &max1(const string &l, const string &r)
{
	if (l.size() > r.size())
		return l;
	else
	{
		if (l.size() < r.size())
			return r;
		else
		{
			if (l > r)
				return l;
			else return r;
		}
	}
}
string dp[41][7];
int main()
{
	
	string s;
	int N;
	int K;
	cin >> N >> K>>s;
	for (int i = 1; i <= N; ++i)
	{
		dp[i][0] = s.substr(0, i);
	}
	/*
	for (int i = 1; i <= N; ++i)
	{
		for (int k = 1;k<=i ; ++k)
			for(int j=1;j<=K;++j)
				dp[i][j] = max1(dp[i][j], plus1(dp[k][j - 1], num(k, j - k, s)));
	}
	*/
	for (int k = 1; k <= K; ++k)
	{
		
		for (int i = 1; i <=N; ++i)
		{
			for (int j = 1; j <= i - 1; ++j)
			{
				dp[i][k] = max1(dp[i][k], plus1(dp[j][k - 1], num(j,i-1, s)));
			}
		}
	}
	cout << dp[N][K];
	return 0;
}

5.看到注释的代码就心酸(之前经常WA),因为你的目的是要找到最大的值,所以你的k必须要放在最外层。这个和Floyd算法特别相似(仅仅是在实现)。Floyd算法的最外层的循环是不是也是k?这个k表示的借助k点求出从i到j的最小距离(因为k总是需要判断的所以需要在顶层不断地判断,有一个好处是不需要向前,因为向前的话以为者做重复工作。)。