鏈接：登錄—專業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];
}