P3537 [POI2012]SZA-Cloakroom

· · 题解

*P3537 [POI2012]SZA-Cloakroom

POI 合集。

好题，一开始一直在想 \dfrac {nk\log n}{\omega} 的 0/1 背包可行性做法，发现无论如何都不可做。但是背包问题并不一定只能装 0/1，我们要充分发挥 f_i 的值域带来的信息。

由于背包不可删除，所以按顺序将物品加入背包方便回答，故将询问离线处理。

设 f_i 表示要用左端点小于当前位置 p 的所有物品组合出价值 i，所需物品右端点最小值的最大值。其中 p 是不断递增的，与此同时回答对应的询问。

不妨设要加入 (c_i,a_i,b_i)，根据我们的策略有 a_i 递增，转移方程如下：

f_j=\max(f_j,\min(f_{j-c_i},b_i))

对于一次询问 (k_j,l_j,r_j)\ (l_j=s_j,r_j=s_j+m_j)，显然只能用 a_i\leq l_j 的物品，因此对于在加入 a_i 之前先要回答所有 l_j<a_i 的询问才能保证正确性。在此基础上，若 f_{k_j}>r_j 说明可行，否则不可行，这一点结合 f 的定义容易理解。

综上，时间复杂度 \mathcal{O}(nk+q\log q)。

const int N = 1e5 + 5;
int n, q, f[N], ans[N << 4];
pair <pii, int> item[N];
pair <pii, pii> query[N << 4];
int main(){
    cin >> n, f[0] = 1e9;
    for(int i = 1; i <= n; i++) cin >> item[i].se >> item[i].fi.fi >> item[i].fi.se;
    cin >> q, sort(item + 1, item + n + 1);
    for(int i = 1; i <= q; i++)
        query[i].fi.fi = read(), query[i].se.fi = read(),
        query[i].fi.se = read() + query[i].fi.fi, query[i].se.se = i;
    sort(query + 1, query + q + 1);
    for(int i = 1, p = 1; i <= n + 1; i++) {
        while(p <= q && (query[p].fi.fi < item[i].fi.fi || i == n + 1))
            ans[query[p].se.se] = f[query[p].se.fi] > query[p].fi.se, p++;
        for(int k = N - 1; k >= item[i].se; k--)
            cmax(f[k], min(f[k - item[i].se], item[i].fi.se));
    } for(int i = 1; i <= q; i++) puts(ans[i] ? "TAK" : "NIE");
    return flush(), 0;
}