题解 | #相邻不同数字的标记#

题目传送门

相邻不同数字的标记

思路

这是一道入门dp题，看到题目要求是求出最多的分值，那大抵是贪心或dp。

但根据经验，dp更简单，且贪心很可能假。

因此，可得：

设 $d{p}_{i,j}dp\_\{i,j\}$ 为前 $ii$ 个的最多分值，$jj$ 为 $11$ 时代表选择第 $ii$ 个，$jj$ 为 $00$ 时则不选第 $ii$ 个。

那么：

$d{p}_{i,0}=\max (d{p}_{i-1,0},d{p}_{i-1,1})dp\_\{i,0\}=\backslash max(dp\_\{i-1,0\},dp\_\{i-1,1\})$

$if{s}_{i-1}\mathrm{\ne }{s}_{i-2}thend{p}_{i,1}=d{p}_{i-1,0}+a_i+a_{i-1}if\backslash text\{\; \}s\_\{i\; -\; 1\}\backslash ne\; s\_\{i\; -\; 2\}\backslash text\{\; \}then\backslash text\{\; \}dp\_\{i,1\}=dp\_\{i-1,0\}+a\_i+a\_\{i-1\}$

$ans=\max (d{p}_{n,0},d{p}_{n,1})ans=\backslash max(dp\_\{n,0\},dp\_\{n,1\})$

Code

using namespace std;
long long n, a[100005], ans = 0;
long long dp[100005][2] = {0};
string s;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> s;
    for (int i = 2; i <= n; i++)
    {
        if (s[i - 2] != s[i - 1]) dp[i][1] = dp[i - 1][0] + a[i] + a[i - 1];
        dp[i][0] = max(dp[i - 1][1], dp[i - 1][0]);
    }
    cout << max(dp[n][0], dp[n][1]) << endl;
    return 0;
}