2025/03/16蚂蚁笔试第二题思路和代码

思路：动态规划，保证组成的最后字符串中不包含110，那么其实只需要记录当前已经组成的字符串最后的三种状态，分别是0，1，11

对于枚举的新字符如果为0，则可以由状态0->0 / 1->0, 但是如果前面的状态为11则不能转移，因为会组成110与题目要求不符

对于枚举的新字符如果为1，则可以由状态0->1 / 1->11 / 11->11 这三种状态转移

按照上述分析进行转移即可

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main() {
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; i++) cin >> arr[i];
    vector<vector<ll>> f(n, vector<long long>(3, -1));
    string s;
    cin >> s;
    if (s[0] == '0') f[0][0] = arr[0];
    else if (s[0] == '1') f[0][1] = arr[0];
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < 3; j++) f[i][j] = f[i - 1][j];
        if (s[i] == '0') {
            f[i][0] = max(f[i][0], arr[i]);
            if (f[i - 1][0] != -1 || f[i - 1][1] != -1) {
                f[i][0] = max(f[i][0], max(f[i - 1][0], f[i - 1][1]) + arr[i]);
            }
        } else {
            f[i][1] = max(f[i][1], arr[i]);
            if (f[i - 1][0] != -1) {
                f[i][1] = max(f[i - 1][0] + arr[i], f[i][1]);
            }
            if (f[i - 1][1] != -1 || f[i - 1][2] != -1) {
                f[i][2] = max(max(f[i - 1][1], f[i - 1][2]) + arr[i], f[i][2]);
            }
        }
    }
    ll ans = 0;
    for (int i = 0; i < 3; i++) ans = max(f[n - 1][i], ans);
    cout << ans << endl;
    return 0;
}