D题dp做法

dp的方法感觉更通用些，可以推广到举手数更多的情况，可惜赛时d了半天也没d出来。。。

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

typedef long long LL;
typedef unsigned long long ULL;

constexpr int INF = 0x3f3f3f3f;
constexpr int MOD = 1e9 + 7;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int n;
    cin >> n;

    string s;
    cin >> s;
    
    // 预处理前缀‘1’的数目，方便待会计算输赢次数
    vector<int> pre(n + 1);
    for (int i = 1; i <= n; i++) {
        pre[i] = pre[i - 1] + (s[i - 1] == '1');
    }

    LL ans = 0;
    vector<vector<vector<LL>>> memo(n, vector<vector<LL>>(3, vector<LL>(3, -1)));

    // dfs(i, cnt, add) 表示下标为 i 时，还有 cnt 次举手机会，
    // 并且已经在 i 之前的 add 个 '0' 处使用了举手机会情况下，符合条件“任意时刻胜场数量不小于负场数量”的
    // 举手方案总数
    auto dfs = [&](auto self, int i, int cnt, int add) -> LL {
        if (i >= n) {
            return 1;
        }

        if (memo[i][cnt][add] != -1) {
            return memo[i][cnt][add];
        }

        LL res = 0;
        int win = pre[i] + add + (s[i] == '1');     // 由于已经在 i 之前的 add 个 '0' 处使用了举手机会，故胜场数需要加上 add
        int lose = i + 1 - win;                    
        if (win < lose) {   // 胜场数小于负场数，则此次一定要用一次举手机会
            if (cnt > 0) {
                res += self(self, i + 1, cnt - 1, add + (s[i] == '0'));
                memo[i][cnt][add] = res;
                return memo[i][cnt][add];
            } else {
                memo[i][cnt][add] = 0;
                return 0;
            }
        }

        res += self(self, i + 1, cnt, add);     // 不举手
        if (cnt > 0) {
            res += self(self, i + 1, cnt - 1, add + (s[i] == '0'));     // 举手
        }

        memo[i][cnt][add] = res;
        return res;
    };

    // 由于题目要求的是“恰好”有 2 局是举手的，而 dfs(dfs, 0, 2, 0) 算的是所有方案数
    // 故需要减去举手数小于等于1的情况
    cout << dfs(dfs, 0, 2, 0) - dfs(dfs, 0, 1, 0) << '\n';
    return 0;
}