8.26华为机试第二题，动态规划求解

#include<iostream>
#include<vector>
#include<string>
#include<unordered_map>
#include<algorithm>
using namespace std;
int maxMJ_DP(string str, vector<int>wide, vector<int>high)
{
	int len = str.size();
	int len_r = (len - 5 + 2) / 4;
	int a = 0;
	int max_high = 0;
	int max_mj = 0;
	for (int i = 0; i < len; i++)
	{
		if (str[i] == '-')return 0;//出现负号，那么不合法
		if (i < len / 2 && isdigit(str[i]))
		{
			wide[a] = str[i] - '0';
			if (wide[a] < 0) return 0;
			a++;
		}
		else
		{
			if (i > len / 2 && isdigit(str[i]))
			{
				high[a - len_r] = str[i] - '0';
				max_high = max_high > high[a - len_r] ? max_high : high[a - len_r];
				a++;
			}
		}
	}
	vector<vector<int>>dp(high.size(), vector<int>(max_high, 0));//每个元素dp[i][j]表示以当前矩形i+1箱子为终点，高度为（j+1）时面积的最大值
	//初始化
	for (int i = 0; i < high[0]; i++)
	{
		dp[0][i] = wide[0] * (i + 1);
		max_mj = max(max_mj, dp[0][i]);
	}
	//状态转移，可空间优化
	for (int i = 1; i < len_r; i++)
	{
		for (int j = 0; j < high[i]; j++)
		{
			if (j + 1 <= high[i - 1])
				dp[i][j] = dp[i - 1][j] + wide[i] * (j + 1);
			else
				dp[i][j] = wide[i] * (j + 1);
			max_mj = max(max_mj, dp[i][j]);
		}
	}
	return max_mj;
}
int main()
{
	//输入 [1,1,1,1,-2,1,1],[5,2,5,4,5,1,6]
	string str;
	cin >> str;
	int len = str.size();
	//处理输入
	int len_r = (len - 5 + 2) / 4;
	vector<int>wide(len_r);
	vector<int>high(len_r);
	int sum = maxMJ_DP(str, wide, high);
	cout << sum;
	return 0;
}