相邻不同数字的标记
链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
时间限制：C/C++ 1秒，其他语言2秒
空间限制：C/C++ 262144K，其他语言524288K
64bit IO Format: %lld
题目描述
小红拿到了一个数组，每个数字被染成了红色或蓝色。
小红有很多次操作，每次操作可以选择两个相邻的不同颜色的数字标记，并获得它们数字之和的得分。已经被标记的数字无法再次标记。
小红想知道，自己最多能获得多少分。
输入描述:
第一行输入一个正整数 nnn ，代表数组的长度。 第二行输入 nnn 个正整数 aia_iai，代表小红拿到的数组。
第三行输入一个仅包含 'R' 和 'B' 的字符串，第 iii 个字符为 'R' 代表数组第 iii 个数被染成红色，'B'代表被染成蓝色。
1≤n≤1051\leq n \leq 10^51≤n≤105
1≤ai≤1091\leq a_i \leq 10^91≤ai≤109
输出描述:
输出一个整数，表示小红最多能获得的分值。
示例1
输入
复制5 1 3 2 6 5 BRRBB
5 1 3 2 6 5 BRRBB
输出
复制12
12
说明
第一次选择标记第一个数和第二个数，标记的数是1和3。 第二次选择标记第三个数和第四个数，标记的数是2和6。 总得分为1+3+2+6=12
看到求最大又是一个不可排序的段，马上想到用dp写，写dp走dp五部曲。
1.确定dp数组的含义
这道题目的dp数组的含义比较好看出来，dp【i】就是前i个可取的情况下能取到的最大值。dp数组一般比较简单的就是直接去看题目要求的是什么。
2.确定递推公式
由于第i项可以由前面的i-1项和i-2项推出来，dp[i]=max(dp[i-1],dp[i-2]+a[i-1]+a[i]),有些同学可能没法理解到，其实就是第i项的前一项选和不选，应为每次会加上两个数值。
3.初始化dp数组
dp【0】就是0，1项啥都没有嘛，dp【1】是在第一的第二项颜色不同时前两项数值的相加。其余项都初始化为0。
4.确定遍历顺序
后面的值都是由前面的推出来，就是由前向后遍历。
5.打印dp数组
如果答案不对打印dp数组检查。
#include<iostream>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<string>
#include<vector>
#include<math.h>
#include<iomanip>
#include<set>
#include<queue>
#include<stack>
#include<map>
#include<list>
#include <stdlib.h>
#include<deque>
#include <stdlib.h>
#include <time.h>
#include<cstdlib>
using namespace std;
long long n, a[1000000];
string c;
long long dp[1000000];
int main()
{
cin >> n;
for (int i = 0; i < n; i++)
{
cin >> a[i];
}
cin >> c;
dp[0] = 0;
if (c[0] != c[1])
{
dp[1] = a[0] + a[1];
}
for (int i = 2; i < n; i++)
{
if (c[i] != c[i - 1])
{
dp[i] = max(dp[i - 1], dp[i - 2] + a[i] + a[i - 1]);
}
else
{
dp[i] = dp[i - 1];
}
}
cout << dp[n - 1];
}原文地址：https://blog.csdn.net/Q210617/article/details/140279528
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！