链接：httpsacnowcodercomacmcontest60456B来源：牛客网小红拿到了一个数组每个数字被染成了红色或蓝色。小红有很多次操作每次操作可以选择两个相邻的不同颜色的数字标记并获得它们数字之和的得分。已经被标记的数字无法再次标记。小红想知道自己最多能获得多少分。用C++实现

#include #include using namespace std;

int getMaxScore(vector& nums) { int n = nums.size(); vector<vector> dp(n, vector(n, 0)); for (int len = 2; len <= n; len++) { for (int i = 0; i <= n - len; i++) { int j = i + len - 1; if (nums[i] != nums[j]) { for (int k = i; k < j; k++) { dp[i][j] = max(dp[i][j], dp[i][k] + dp[k + 1][j] + nums[i] + nums[j]); } } } } return dp[0][n - 1]; }

int main() { int n; cin >> n; vector nums(n); for (int i = 0; i < n; i++) { cin >> nums[i]; } int ans = getMaxScore(nums); cout << ans << endl; return 0;