题解：P10884 [COCI 2017/2018 #2] San

dangerous_tDp · 2026-04-24 17:56:37 · 题解

较典的折半搜索。

看到 n \le 40，可以果断使用折半搜索以优化复杂度，也就是将楼拆成前后两半部分，对于每部分暴力枚举出可能的路径并统计；再将两半部分合并统计跨区域的方案数，这里可以使用二分实现。

对于具体实现，有两种方式如下：

:::success[类 dfs]

参照此题解，拜谢巨佬作者。

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50;
int n, k, m, h[N], g[N], ans;
vector<int> pre[N];
signed main(){
    ios::sync_with_stdio(0), cin.tie(0);
    cin >> n >> k, m = n / 2;
    for (int i = 1; i <= n; i ++)cin >> h[i] >> g[i];
    for (int i = 1; i <= m; i ++){
        for (int j = 0; j < i; j ++)
                if (h[j] <= h[i])
                    for (auto v : pre[j])
                        pre[i].push_back(v + g[i]);
        pre[i].push_back(g[i]);
    }for (int i = n; i > m; i --){
        for (int j = n + 1; j > i; j --)
                if (h[j] >= h[i])
                    for (auto v : pre[j])
                        pre[i].push_back(v + g[i]);
        pre[i].push_back(g[i]);
    }for (int i = 1; i <= n; i ++)
        sort(pre[i].begin(), pre[i].end());
    for (int i = 1; i <= m; i ++)
        ans += pre[i].size() - (lower_bound(pre[i].
        begin(), pre[i].end(), k) - pre[i].begin());
    for (int i = n; i > m; i --){
        for (int j = 1; j <= m; j ++)
            if (h[j] <= h[i])
                for (auto v : pre[i])
                    ans += pre[j].size() - (lower_bound(pre[j].
                    begin(), pre[j].end(), k - v) - pre[j].begin());
        ans += pre[i].size() - (lower_bound(pre[i].
        begin(), pre[i].end(), k) - pre[i].begin());
    }
    return cout << ans, 0;
}

:::

:::success[类状压]

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N = 50;
int n, k, h[N], g[N], ans;
vector<int> pre[N];
signed main(){
    ios::sync_with_stdio(0), cin.tie(0), cin >> n >> k;
    for (int i = 1; i <= n; i ++)cin >> h[i] >> g[i];
    int m = n / 2, l = n - m;h[n + 1] = 1e9;
    for (int i = 0; i < (1 << m); i ++){
        int nh = 0, s = 0, f = 0, lst = 0;
        for (int j = 1; j <= m; j ++){
            if ((1 << j - 1) & i)
                if (h[j] >= nh)nh = h[j], s += g[j], lst = j;
                else{f = 1;break;}
        }
        if (f)continue;pre[lst].push_back(s);
    }for (int i = 1; i <= m; i ++)
        sort(pre[i].begin(), pre[i].end()),
        ans += pre[i].size() - (lower_bound(pre[i]
        .begin(), pre[i].end(), k) - pre[i].begin());
    for (int i = 0; i < (1 << l); i ++){
        int nh = 0, s = 0, f = 0, fi = n + 1;
        for (int j = 1; j <= l; j ++){
            if ((1 << j - 1) & i)
                if (h[j + m] >= nh)
                    nh = h[j + m], s += g[j + m],
                    fi = (fi == n + 1 ? j + m : fi);
                else{f = 1;break;}
        }if (f || fi == n + 1)continue;ans += s >= k;
        for (int j = 1; j <= m; j ++)
            if (h[j] <= h[fi])
                ans += pre[j].size() - (lower_bound(pre[j].
                begin(), pre[j].end(), k - s) - pre[j].begin());
    }return cout << ans, 0;
}

:::

应该比较好理解，不懂私。