3864. Minimum Cost to Partition a Binary String

You are given a binary string s and two integers encCost and flatCost.

For each index i, s[i] = '1' indicates that the i^th element is sensitive, and s[i] = '0' indicates that it is not.

The string must be partitioned into segments. Initially, the entire string forms a single segment.

For a segment of length L containing X sensitive elements:

• If X = 0, the cost is flatCost.
• If X > 0, the cost is L * X * encCost.

If a segment has even length, you may split it into two contiguous segments of equal length and the cost of this split is the sum of costs of the resulting segments.

Return an integer denoting the minimum possible total cost over all valid partitions.

int pre[101010];
class Solution {
    long long dnc(int l, int r, long long e, long long f) {
        long long len = r - l + 1;
        long long x = pre[r+1] - pre[l];
        long long res = x ? len * x * e : f;
        if(len % 2) return res;
        return min(res, dnc(l, l + len / 2 - 1, e, f) + dnc(l + len / 2, r, e, f));
    }
public:
    long long minCost(string s, int encCost, int flatCost) {
        for(int i = 0; i < s.length(); i++) pre[i+1] = pre[i] + (s[i] == '1');
        return dnc(0,s.length() - 1, encCost, flatCost);
    }
};