相邻不同数字的标记——DP

2023-12-13 09:33:21

小红拿到了一个数组,每个数字被染成了红色或蓝色。
小红有很多次操作,每次操作可以选择两个相邻的不同颜色的数字标记,并获得它们数字之和的得分。已经被标记的数字无法再次标记。
小红想知道,自己最多能获得多少分。

Input
第一行输入一个正整数 n (1 ≤ n ≤ 1e5),代表数组长度。
第二行输入 n 个正整数 ai (1 ≤ ai ≤ 1e9),代表小红拿到的数组。
第三行输入一个仅包含 'R' 和 'B' 的字符串,第 i 个字符为 'R' 代表第 i 个数被染成红色,'B' 被染成蓝色。

Output?
输出一个整数,表示小红最多能获得的分值。

输入
5
1 3 2 6 5
BRRBB

输出
12

解析:
考虑是否合并.
假设我们i和i-1的颜色不同,那么我们合并的话就是从i-2的权重转移过来,如果我们不合并是从i-1的权重转移而来,所以我们定义为i结尾个位置的最大权重为多少.

#include <bits/stdc++.h>
using namespace std;
#define int long long 
#define ios ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
typedef pair<int,int> PII;
const int N=2e6+10;
int n;
int a[N],f[N];
string s;
signed main()
{
    ios;
    cin>>n;
    for (int i=0;i<n;i++) cin>>a[i];
    cin>>s;
    for (int i=1;i<n;i++)
    {
        f[i]=f[i-1];
        if (s[i]!=s[i-1]) f[i]=max(f[i],f[i-2]+a[i]+a[i-1]);
    }
    cout<<f[n-1];
    return 0;
}

文章来源:https://blog.csdn.net/m0_74403543/article/details/134953897
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。