Cvent

01Maximize Score

You are given a string S and an integer array of size N. You need to maximize your score by performing the following operation multiple times until the string S is empty: Choose a substring from S where all characters are identical. Calculate the length of this substring, called size. Add the sizeth element from the array arr to your total score. Remove the selected substring from S. Continue this process until the string S is empty, and return the maximum possible score.

Example 1

Input:

S = "abbbac"
arr = [2, 5, 3, 1, 7]

Output:

Explanation: abbbac -> abac -> aac -> c -> "" 5 + 2 + 5 + 2 = 14

解法

把 S 切成相同字符的 run，每个 run 长度 L 可任意拆分成若干段，求 max sum arr[size_i] s.t. sum size_i = L。这是无界背包：对每个 run 单独跑一次 dp[L] = max(dp[L-k] + arr[k-1])。各 run 独立累加。设 M = max run length，时间 O(N·M)，空间 O(M)。

from typing import List

def maximize_score(S: str, arr: List[int]) -> int:
    # group into runs
    runs = []
    i = 0
    while i < len(S):
        j = i
        while j < len(S) and S[j] == S[i]:
            j += 1
        runs.append(j - i)
        i = j

    total = 0
    for L in runs:
        # unbounded knapsack: dp[x] = best score using pieces of length 1..L summing to x
        dp = [0] * (L + 1)
        for x in range(1, L + 1):
            best = 0
            for k in range(1, x + 1):
                if k - 1 < len(arr):
                    best = max(best, dp[x - k] + arr[k - 1])
            dp[x] = best
        total += dp[L]
    return total

class Solution {
    public int maximizeScore(String S, int[] arr) {
        int total = 0, n = S.length();
        int i = 0;
        while (i < n) {
            int j = i;
            while (j < n && S.charAt(j) == S.charAt(i)) j++;
            int L = j - i;
            int[] dp = new int[L + 1];
            for (int x = 1; x <= L; x++) {
                int best = 0;
                for (int k = 1; k <= x && k - 1 < arr.length; k++) {
                    best = Math.max(best, dp[x - k] + arr[k - 1]);
                }
                dp[x] = best;
            }
            total += dp[L];
            i = j;
        }
        return total;
    }
}

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    int maximizeScore(string S, vector<int>& arr) {
        int total = 0, n = S.size(), i = 0;
        while (i < n) {
            int j = i;
            while (j < n && S[j] == S[i]) j++;
            int L = j - i;
            vector<int> dp(L + 1, 0);
            for (int x = 1; x <= L; x++) {
                int best = 0;
                for (int k = 1; k <= x && k - 1 < (int)arr.size(); k++) {
                    best = max(best, dp[x - k] + arr[k - 1]);
                }
                dp[x] = best;
            }
            total += dp[L];
            i = j;
        }
        return total;
    }
};