说是动态规划,其实有些暴力。
有时间再描述题目
#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; }
全部评论
(2) 回帖