[HFOJ 1555] 题解

大意

最初 $x = s$, 然后进行 $k$ 个操作, 每次 $x \leftarrow x + a_i$ 或者 $x \leftarrow x - a_i$ ,
同时要求 $0 \le x \le n$, 最后, 求 $max(x)$ .

题解

分成两部分, 先求出 $k = \frac m 2$ 时的所有情况, 记为 $x$.

然后, $s := 0$ , 再求出剩下情况, 对于每种情况 $y$ , 最大 $h$ , 最小 $l$ , 找到最大的 $x$ 使得 $0 \le x + l \le maxdepth, 0 \le x + h \le maxdepth$ , 即 $-l \le x \le maxdepth - h$ .

void dfs1(ll x, ll i)
{
    if (x > max_dep || x < 0) return;
    if (i > half) {
        pos[++cnt] = x;
        return;
    }
}

pair<ll, ll> find(ll l, ll h)
{
    ll l_pos = lower_bound(pos + 1, pos + 1 + cnt, l) - pos;
    ll h_pos = upper_bound(pos + 1, pos + 1 + cnt, h + 1) - pos;
    return { pos[l_pos], pos[h_pos - 1] };
}

void dfs2(ll x, ll l, ll h, ll i)
{
    if (i > n) {
        pair<ll, ll> y = find(-l, max_dep - h);
        if (x + y.first >= 0) res_min = min(res_min, x + y.first);
        if (x + y.second <= max_dep) res_max = max(res_max, x + y.second);
        return;
    }
    ...
}