相邻不同数字的标记——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
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!